Find all combinations of a given set of numbers

Question

say I have a set of numbers '0', '1', '2', ..., '9'. I want to find all numbers that contain exactly one of each of the numbers in my set.

The problem is: Before I start my program, I do not know how many numbers and which numbers my set will include. (For example, the set could include the numbers '1', '3' and '14'.)

I searched the internet, and stumbled upon the term 'dynamic programming' which apparently is something to use to solve problems like mine, but I did not understand the examples.

Can somebody give me a hint on how to solve this problem (possibly with dynamic programming)?

EDIT: When the set includes numbers like '14' the different numbers of the set would of course have to be separated by some means, e.g. when the set includes the numbers '1', '3', and '14', combinations could be something like 1-3-14 or 3-14-1 (= individual numbers separated by a '-'-character).

EDIT 2: One problem that seems to be somewhat similar is described here: one of the solutions uses dynamic programming.

Answer 1

To me, it looks like you are looking for all permutations of a given set of elements.

If you use C++ there is a standard function next_permutation() that does exactly what you are looking for. You start with the sorted array and then call next_permutation repeatedly.

The example is here: http://www.cplusplus.com/reference/algorithm/next_permutation/

Answer 2

To examine all the combinations without knowing in advance how many digits must have the output, I once wrote this code:

#include <stdio.h>
#include <stdlib.h>

#define ARRSIZE(arr)    (sizeof(arr)/sizeof(*(arr)))

int main()
{
    const char values[]= {'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
    char * buffer=NULL;
    int * stack=NULL;
    int combinationLength=-1;
    int valuesNumber=-1;
    int curPos=0;
    fprintf(stderr, "%s", "Length of a combination: ");
    if(scanf("%d", &combinationLength)!=1 || combinationLength<1)
    {
        fputs("Invalid value.\n",stderr);
        return 1;
    }
    fprintf(stderr, "%s (%lu max): ", "Possible digit values",(long unsigned)ARRSIZE(values));
    if(scanf("%d", &valuesNumber)!=1 || valuesNumber<1 || (size_t)valuesNumber>ARRSIZE(values))
    {
        fputs("Invalid value.\n", stderr);
        return 1;
    }
    buffer=(char *)malloc(combinationLength);
    stack=(int *)malloc(combinationLength*sizeof(*stack));
    if(buffer==NULL || stack==NULL)
    {
        fputs("Cannot allocate memory.\n", stderr);
        free(buffer);
        free(stack);
        return 2;
    }
    /* Combinations generator */
    for(;;)
    {
        /* If we reached the last digit symbol... */
        if(stack[curPos]==valuesNumber)
        {
            /* ...get back to the previous position, if we finished exit */
            if(--curPos==-1)
                break;
            /* Repeat this check */
            continue;
        }
        buffer[curPos]=values[stack[curPos]];
        /* If we are in the most inner fake-cycle write the combination */
        if(curPos==combinationLength-1)
            puts(buffer);
        stack[curPos]++;
        /* If we aren't on the last position, start working on the next one */
        if(curPos<combinationLength-1)
        {
            curPos++;
            stack[curPos]=0;
        }
    }
    /* Cleanup */
    free(buffer);
    free(stack);
    return 0;    
}

It does everything just in one cycle to avoid recursion and function calls overhead, still if "fakes" the needed nested for loops using the stack array.
It performs quite well, on my 4 years old Athlon64 3800+ it takes 2' 4" of user time (=> actual computation time) to generate 36^6=2176782336 combinations, so it computes about 17.5 million combinations per second.

matteo@teoubuntu:~/cpp$ gcc -Wall -Wextra -ansi -pedantic -O3 combinations.c -o combinations.x
matteo@teoubuntu:~/cpp$ time ./combinations.x > /media/Dati/combinations.txt
Length of a combination: 6
Possible digit values (36 max): 36

real    13m6.685s
user    2m3.900s
sys 0m53.930s
matteo@teoubuntu:~/cpp$ head /media/Dati/combinations.txt
000000
000001
000002
000003
000004
000005
000006
000007
000008
000009
matteo@teoubuntu:~/cpp$ tail /media/Dati/combinations.txt
zzzzzq
zzzzzr
zzzzzs
zzzzzt
zzzzzu
zzzzzv
zzzzzw
zzzzzx
zzzzzy
zzzzzz
matteo@teoubuntu:~/cpp$ ls -lh /media/Dati/combinations.txt 
-rwxrwxrwx 1 root root 15G 2010-01-02 14:16 /media/Dati/combinations.txt
matteo@teoubuntu:~/cpp$ 

The "real" time is quite high because I was also doing something else on the PC in the meanwhile.

Answer 3

You're looking to find all permutations of a given set of values.

One article on "doing" permutations in Java is here: http://www.bearcave.com/random_hacks/permute.html

You want to skip the first couple of sections until you get to the heading Permutation algorithms (of course).

Answer 4

Here is my C# 3.0 implementation of permutations you can find useful

public static class PermutationExpressions
    {
        public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> list)
        {
            return list.Permutations((uint)list.Count());
        }

        public static IEnumerable<IEnumerable<T>> Permutations<T>(this IList<T> list)
        {
            return list.Permutations((uint)list.Count);
        }

        private static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> list, uint n)
        {
            if (n < 2) yield return list;
            else
            {
                var ie = list.GetEnumerator();
                for (var i = 0; i < n; i++)
                {
                    ie.MoveNext();
                    var item = ie.Current;

                    var i1 = i;
                    var sub_list = list.Where((excluded, j) => j != i1).ToList();

                    var sub_permutations = sub_list.Permutations(n - 1);

                    foreach (var sub_permutation in sub_permutations)
                    {
                        yield return
                            Enumerable.Repeat(item, 1)
                                .Concat(sub_permutation);
                    }
                }
            }
        }
        }

[TestFixture]
    public class TestPermutations
    {
        [Test]
        public void Permutation_Returns_Permutations()
        {
            var permutations = PermutationExpressions.Permutations(new[] { "a", "b", "c" }.AsEnumerable());
            foreach (var permutation in permutations)
            {
                Console.WriteLine(string.Join("", permutation.ToArray()));
            }
            Assert.AreEqual("abc_acb_bac_bca_cab_cba", permutations.Select(perm => perm.joinToString("")).joinToString("_"));
        }
    }

Answer 5

How many numbers, and which ones, aren't two questions. If you know which numbers, you know how many.

And the names of the numbers aren't very interesting. 1-3-14 or 0-1-2 or Foo-Bar-Baz - it is always the same problem, the same problem as the permutations of 0-1-2 and with an array, where to look up the result.

idx nums words
0   1     foo
1   3     bar
2   14    baz

The most convenient solution is, to write a generic Iterable. Then you can use the simplified for-loop, to access each permutation.

import java.util.*;

class PermutationIterator <T> implements Iterator <List <T>> {

    private int  current = 0;
    private final long last;
    private final List <T> lilio;

    public PermutationIterator (final List <T> llo) {
        lilio = llo;
        long product = 1;
        for (long p = 1; p <= llo.size (); ++p) 
            product *= p; 
        last = product;
    }

    public boolean hasNext () {
        return current != last;
    }

    public List <T> next () {
        ++current;
        return get (current - 1, lilio);
    }

    public void remove () {
        ++current;
    }

    private List <T> get (final int code, final List <T> li) {
        int len = li.size ();
        int pos = code % len;
        if (len > 1) {
            List <T> rest = get (code / len, li.subList (1, li.size ()));
            List <T> a = rest.subList (0, pos);
            List <T> res = new ArrayList <T> ();
            res.addAll (a);
            res.add (li.get (0));
            res.addAll (rest.subList (pos, rest.size ()));
            return res;
        }
        return li;
    }
}

class PermutationIterable <T> implements Iterable <List <T>> {

    private List <T> lilio; 

    public PermutationIterable (List <T> llo) {
        lilio = llo;
    }

    public Iterator <List <T>> iterator () {
        return new PermutationIterator <T> (lilio);
    }
}

class PermutationIteratorTest {

    public static void main (String[] args) {
        List <Integer> la = Arrays.asList (new Integer [] {1, 3, 14});
        PermutationIterable <Integer> pi = new PermutationIterable <Integer> (la);
        for (List <Integer> lc: pi)
            show (lc);
    }

    public static void show (List <Integer> lo) {
        System.out.print ("(");
        for (Object o: lo)
            System.out.print (o + ", ");
        System.out.println (")");
    }
}

Answer 6

Nothing to do with dynamic programming; unless you want to wear underpants outside your trousers and paint a symbol on your chest.

Simple way to do it is maintain an array of 0-9 of integers, then run through the numbers one by one and increment array[num]. The result, once you've processed all digits, is to see if any element of the array is non-zero or one. (That indicates a repeated digit.) Of course, it's trivial to take a number and then iterate through digit by digit using modulus and divisor.

Answer 7

So, let's say you have the numbers 1, 2 and 3.

If you are expecting the six numbers 123, 132, 213, 231, 312 and 321 to be the correct answer, what you're looking for is some code to generate all permutations of a set, that'll be faster than almost anything else for problems of an interesting size. You're looking at O(n!) as a best case, though.

Answer 8

You should write a recursive function that loops through the list and every time calls itself with an updated list. This means it needs to create a copy of the list with N-1 elements to pass to the next iteration. For results, you need to append the currently selected number in each iteration.

string Permutations(List numbers, string prefix)
{
   foreach (current_number in numbers)
   {
      new_prefix = prefix+"-"+number;
      new_list=make_copy_except(numbers,  current_number)
      if (new_list.Length==0)
           print new_prefix
      else
           Permutations(new_list, new_prefix)
   }
}

Answer 9

import Data.List (inits, tails)

place :: a -> [a] -> [[a]]
place element list = zipWith (\front back -> front ++ element:back)
                             (inits list)
                             (tails list)

perm :: [a] -> [[a]]
perm = foldr (\element rest -> concat (map (place element) rest)) [[]]

test = perm [1, 3, 14]