Find all combinations of a given set of numbers

Question

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

The problem is this: before I run my program, I do not know how many numbers and which numbers my set will include. (For example, a set may include the numbers "1", "3", and "14".)

I searched the Internet and came across the term “dynamic programming”, which, apparently, can use something to solve problems like mine, but I did not understand the examples.

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

EDIT: When a dial-up includes numbers like "14", different dial-up numbers, of course, should be separated in some way, for example. when the set includes the numbers “1”, “3” and “14”, the combinations can be approximately 1-3-14 or 3-14-1 (= individual numbers separated by “- '").

EDIT 2: One of the problems, which seems somewhat similar, is described here : one of the solutions uses dynamic programming.

Answer 1

To check all the combinations without knowing in advance how many digits the output should have, 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 in only one cycle to avoid the overhead of recursion and function, but if it "fakes" the necessary nested for loops using the stack array.
It works pretty well, on my 4-year-old Athlon64 3800+ it takes 2 '4 "user time (=> actual calculation time) to generate 36 ^ 6 = 2176782336 combinations, so it calculates 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 pretty high, because at that time I was also doing something else on the PC.

Answer 2

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

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

Example here: http://www.cplusplus.com/reference/algorithm/next_permutation/

Answer 3

You are looking for 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 implementation of C # 3.0 permutations you may 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 are not two questions. If you know what numbers, you know how many.

And the names of numbers are not very interesting. 1-3-14 or 0-1-2 or Foo-Bar-Baz is always the same problem, the same problem as permutations 0-1-2 and with the array where to look for the result.

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

The most convenient solution is to write a generic Iterable. You can then 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; if you do not want to wear underpants outside the trousers and draw a symbol on the chest.

A simple way is to maintain an array of 0-9 integers, and then number the numbers one by one and increase the array [num]. The result, as soon as you have processed all the digits, is to see if any element of the array is non-zero or one. (This indicates a repeated digit.) Of course, it is trivial to take a number, and then iterate over a digit with a number using the module and divider.

Answer 7

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

If you expect the six numbers 123, 132, 213, 231, 312 and 321 to be the correct answer, then what you are looking for is some code to generate all the permutations of the set, which will be faster than almost anything else for problems interesting size. However, you are looking at O ​​(n!) As the best option.

Answer 8

You must write a recursive function that iterates over the list and calls itself each time with an updated list. This means that he needs to create a copy of the list with elements N-1 in order to proceed to the next iteration. To get the results you need to add the current selected number at 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]