基于 2 个变量的组合

Question

我想要完成的是为以下内容创建一个函数：

想象一下我有 1-9 个正方形。这些方块有一个全局编号，而不是单独编号。它们就像一个集合，而那个集合有这个数字。

例如：| _ | _ | _ | 19

我想做的是一个函数，它根据方块的数量和与它们相关的数字给出可能的组合。对于上面的示例：9、8、2 是可能的组合之一。然而，我只想要这些组合中的数字，而不是组合本身。另外，它们必须是唯一的（不应该是 9, 9, 1）。哦，这些数字范围仅为 1-9。

我怎样才能在C中实现这一点？如果您想知道这是一款益智游戏。

提前致谢！

Answer 1

看起来您正在尝试查找右侧整数的受限分区。该链接应该为您提供一个良好的起点，并且您应该能够找到一些将整数分区生成任意数量部分的算法。

Answer 2

为了将来的参考，在组合学中，我们说“顺序无关紧要”，意思是“我只想要一组数字，而不是特定的顺序”

//Sets the given digit array to contain the "first" set of numbers which sum to sum
void firstCombination(int digits[], int numDigits, int sum) { 
    reset(digits, 0, 1, numDigits, sum);
}

//Modifies the digit array to contain the "next" set of numbers with the same sum.
//Returns false when no more combinations left
int nextCombination(int digits[], int numDigits) {
    int i;
    int foundDiffering = 0;
    int remaining = 0;
    for (i = numDigits - 1; i > 0; i--) {
        remaining += digits[i];
        if (digits[i] - digits[i - 1] > 1) {
            if (foundDiffering || digits[i] - digits[i - 1] > 2) {
                digits[i - 1]++;
                remaining--;
                break;
            } else
                foundDiffering = 1;
        }
    }
    if (i == 0)
        return 0;
    else {
        reset(digits, i, digits[i - 1] + 1, numDigits - i, remaining);
        return 1;
    }
}

//Helper method for firstCombination and nextCombination
void reset(int digits[], int off, int lowestValue, int numDigits, int sum) {
    int i;
    int remaining = sum;
    for (i = 0; i < numDigits; i++) {
        digits[i + off] = lowestValue;
        remaining -= lowestValue;
        lowestValue++;
    }
    int currentDigit = 9;
    for (i = numDigits + off - 1; i >= off; i--) {
        if (remaining >= currentDigit - digits[i]) {
            remaining -= currentDigit - digits[i];
            digits[i] = currentDigit;
            currentDigit--;
        } else {
            digits[i] += remaining;
            break;
        }
    }
}

Answer 3

听起来你正在做的事情与kakuro非常相似，也称为交叉求和：http:// en.wikipedia.org/wiki/Cross_Sums

有一些用于此类谜题的生成器，例如： http://www.perlmonks.org/?node_id=550884

我怀疑大多数 kakuro 生成器都必须解决您的确切问题，因此您可能会查看一些以获取灵感。