Combinations based on 2 variables

What I'm trying to accomplish is making a function to the following:

Imagine that I have between 1-9 squares. Those squares have a number assigned to them globally, not individually. They are like a set, and that set has this number.

E.g.: | _ | _ | _ | 19

What I'm trying to do is a function that gives me the possible combinations depending on number of squares and the number associated with them. For the example above: 9, 8, 2 is one of the possible combinations. However I just want the numbers that are in those combinations, not the combinations themselves. Plus they have to be unique (shouldn't be 9, 9, 1). Oh and those numbers range from 1-9 only.

How can I achieve this in C? If you are wondering this is for a puzzle game.

Thanks in advance!

Answers


For future reference, in combinatorics we say "order doesn't matter" to mean "I only want the set of numbers, not a specific ordering"

//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;
        }
    }
}

Looks like you are trying to find a restricted Partition of the integer on the right. The link should give you a good starting place, and you should be able to find some algorithms that generate partitions of an integer into an arbitrary number of parts.


It sounds like what you're working on is very similar to kakuro, also know as Cross Sums: http://en.wikipedia.org/wiki/Cross_Sums

There are generators out there for these kinds of puzzles, for example: http://www.perlmonks.org/?node_id=550884

I suspect that most kakuro generators would have to solve your exact problem, so you might look at some for inspiration.


Need Your Help

AsyncTask unfortunately stops on second execution

android android-asynctask arduino

I'm trying to get strings from my Arduino with my Android phone, everything goes well except for when I press my updatebutton the second time, it unfortunately stops.

listen for changes in a textbox

jquery events textbox listener

I'm trying to write some code for a personalised products page on my site. My aim is to have a textbox allowing the user to enter a personal message to go on the product and use jQuery to determi...