Find all possible combinations from 4 input numbers which can add up to 24

Question

Actually, this question can be generalized as below:

Find all possible combinations from a given set of elements, which meets a certain criteria.

So, any good algorithms?

Answer 1

There are only 16 possibilities (and one of those is to add together "none of them", which ain't gonna give you 24), so the old-fashioned "brute force" algorithm looks pretty good to me:

for (unsigned int choice = 1; choice < 16; ++choice) {
    int sum = 0;
    if (choice & 1) sum += elements[0];
    if (choice & 2) sum += elements[1];
    if (choice & 4) sum += elements[2];
    if (choice & 8) sum += elements[3];
    if (sum == 24) {
        // we have a winner
    }
}

In the completely general form of your problem, the only way to tell whether a combination meets "certain criteria" is to evaluate those criteria for every single combination. Given more information about the criteria, maybe you could work out some ways to avoid testing every combination and build an algorithm accordingly, but not without those details. So again, brute force is king.

Answer 2

There are two interesting explanations about the sum problem, both in Wikipedia and MathWorld.

In the case of the first question you asked, the first answer is good for a limited number of elements. You should realize that the reason Mr. Jessop used 16 as the boundary for his loop is because this is 2^4, where 4 is the number of elements in your set. If you had 100 elements, the loop limit would become 2^100 and your algorithm would literally take forever to finish.

In the case of a bounded sum, you should consider a depth first search, because when the sum of elements exceeds the sum you are looking for, you can prune your branch and backtrack.

In the case of the generic question, finding the subset of elements that satisfy certain criteria, this is known as the Knapsack problem, which is known to be NP-Complete. Given that, there is no algorithm that will solve it in less than exponential time.

Nevertheless, there are several heuristics that bring good results to the table, including (but not limited to) genetic algorithms (one I personally like, for I wrote a book on them) and dynamic programming. A simple search in Google will show many scientific papers that describe different solutions for this problem.

Answer 3

Find all possible combinations from a given set of elements, which meets a certain criteria

If i understood you right, this code will helpful for you:

    >>> from itertools import combinations as combi    
    >>> combi.__doc__
'combinations(iterable, r) --> combinations object\n\nReturn successive r-length
 combinations of elements in the iterable.\n\ncombinations(range(4), 3) --> (0,1
,2), (0,1,3), (0,2,3), (1,2,3)'
    >>> set = range(4)
    >>> set
    [0, 1, 2, 3]
    >>> criteria = range(3)
    >>> criteria
    [0, 1, 2]
    >>> for tuple in list(combi(set, len(criteria))):
    ...     if cmp(list(tuple), criteria) == 0:
    ...             print 'criteria exists in tuple: ', tuple
    ...
    criteria exists in tuple:  (0, 1, 2)

    >>> list(combi(set, len(criteria)))
    [(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)]

Answer 4

Generally for a problem as this you have to try all posebilities, the thing you should do have the code abort the building of combiantion if you know it will not satesfie the criteria (if you criteria is that you do not have more then two blue balls, then you have to abort calculation that has more then two). Backtracing

def perm(set,permutation): 
    if lenght(set) == lenght(permutation):
       print permutation
    else:
        for element in set:
           if permutation.add(element) == criteria:
               perm(sett,permutation)
           else:
                permutation.pop()  //remove the element added in the if 

Answer 5

The set of input numbers matters, as you can tell as soon as you allow e.g. negative numbers, imaginary numbers, rational numbers etc in your start set. You could also restrict to e.g. all even numbers, all odd number inputs etc.

That means that it's hard to build something deductive. You need brute force, a.k.a. try every combination etc.

In this particular problem you could build an algoritm that recurses - e.g. find every combination of 3 Int ( 1,22) that add up to 23, then add 1, every combination that add to 22 and add 2 etc. Which can again be broken into every combination of 2 that add up to 21 etc. You need to decide if you can count same number twice.

Once you have that you have a recursive function to call -

combinations( 24 , 4 ) = combinations( 23, 3 ) + combinations( 22, 3 ) + ... combinations( 4, 3 );
combinations( 23 , 3 ) = combinations( 22, 2 ) + ... combinations( 3, 2 );

etc

This works well except you have to be careful around repeating numbers in the recursion.

Answer 6

    private int[][] work()
    {
        const int target = 24;
        List<int[]> combos = new List<int[]>();

        for(int i = 0; i < 9; i++)
            for(int x = 0; x < 9; x++)
                for(int y = 0; y < 9; y++)
                    for (int z = 0; z < 9; z++)
                    {
                        int res = x + y + z + i;
                        if (res == target)
                        {
                            combos.Add(new int[] { x, y, z, i });
                        }
                    }
        return combos.ToArray();
    }

It works instantly, but there probably are better methods rather than 'guess and check'. All I am doing is looping through every possibility, adding them all together, and seeing if it comes out to the target value.

Answer 7

If i understand your question correctly, what you are asking for is called "Permutations" or the number (N) of possible ways to arrange (X) numbers taken from a set of (Y) numbers.

N = Y! / (Y - X)!  

I don't know if this will help, but this is a solution I came up with for an assignment on permutations.

You have an input of : 123 (string) using the substr functions

1) put each number of the input into an array

array[N1,N2,N3,...]

2)Create a swap function

function swap(Number A, Number B)
{
   temp = Number B 
   Number B = Number A   
   Number A = temp   
}

3)This algorithm uses the swap function to move the numbers around until all permutations are done.

original_string= '123'    
temp_string=''

While( temp_string != original_string)
{
   swap(array element[i], array element[i+1])

   if (i == 1)
       i == 0

   temp_string = array.toString
   i++
}

Hopefully you can follow my pseudo code, but this works at least for 3 digit permutations

Answer 8

(n X n ) built up a square matrix of nxn

and print all together its corresponding crossed values

e.g.

1 2 3 4

1 11 12 13 14

2 .. .. .. ..

3 ..

4 .. ..