Комбинации на основе 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, также известное как Cross Sums: http://en.wikipedia.org/wiki/Cross_Sums

Есть генераторы для таких головоломок, например: http://www.perlmonks.org/?node_id=550884

Я подозреваю, что большинству генераторов kakuro придется решать именно вашу проблему, поэтому вы можете взглянуть на некоторые из них для вдохновения.