The Museum of HP Calculators

HP Forum Archive 21

 Question about a "combinations" algorithm Message #1 Posted by Namir on 19 Sept 2012, 4:32 p.m. Hell All, Anyone knows a good link to some (C++, Pascal, BASIC, or Visual Basic) source code to generate different combinations of an array of elements. I am working with a problem where I generate an array of six elements (each being a random value between 1 and 10). I want to be able to generate all possible combinations of these six elements. Thanks! Namir Edited: 19 Sept 2012, 4:32 p.m.

 Re: Question about a "combinations" algorithm Message #2 Posted by Kiyoshi Akima on 19 Sept 2012, 4:47 p.m.,in response to message #1 by Namir Brute-force C/C++: ```{ int a[6]; for (a[0] = 1; a[0] <= 10; a[0]++) for (a[1] = a[0]; a[1] <= 10; a[1]++) for (a[2] = a[1]; a[2] <= 10; a[2]++) for (a[3] = a[2]; a[3] <= 10; a[3]++) for (a[4] = a[3]; a[4] <= 10; a[4]++) for (a[5] = a[4]; a[5] <= 10; a[5]++) { // do whatever } } ```

 Re: Question about a "combinations" algorithm Message #3 Posted by Kiyoshi Akima on 19 Sept 2012, 4:49 p.m.,in response to message #2 by Kiyoshi Akima Or did I misunderstand the problem? My code fragment generates all possible combinations of six numbers each in the range 1 to 10. Are you generating an array of six numbers and then want all the various combinations of those six numbers? All the one-number combinations, all the two-number combinations, and so forth?

 Re: Question about a "combinations" algorithm Message #4 Posted by Namir on 19 Sept 2012, 8:06 p.m.,in response to message #3 by Kiyoshi Akima Yes, I have generated the arrays of six numbers separately. Now I want to create all possible combinations of values based on the values in this array.

 Re: Question about a "combinations" algorithm Message #5 Posted by Marcel Samek on 19 Sept 2012, 4:57 p.m.,in response to message #1 by Namir Just to make the question perfectly clear: 1) Are you talking about combinations or permutations 2) Is repetition of elements allowed? M.

 Re: Question about a "combinations" algorithm Message #6 Posted by Namir on 19 Sept 2012, 8:06 p.m.,in response to message #5 by Marcel Samek Yes you can repeat the elements,

 Re: Question about a "combinations" algorithm Message #7 Posted by Paul Dale on 19 Sept 2012, 5:19 p.m.,in response to message #1 by Namir C++ is easy. The standard template library include this algorithm. ``` #include ``` Then call: ``` next_permutation(array, array+n) or prev_permutation(array, array+n) ``` The algorithm used is well known. - Pauli

 Re: Question about a "combinations" algorithm Message #8 Posted by Marcus von Cube, Germany on 20 Sept 2012, 2:30 p.m.,in response to message #1 by Namir If you allow repetitions I'd just create all 6 digit base 6 numbers and use their digits as indexes into the array of numbers.

 Re: Question about a "combinations" algorithm Message #9 Posted by David Hayden on 20 Sept 2012, 3:31 p.m.,in response to message #1 by Namir Here it is in C++. I think this is the same algorithm as the one Pauli mentioned. The main entry point is permute(). This version calls processResult() on each permutation. ```// Process the results of permuting. This gets called once per permutation. static void processResult(int arr[], int len) { int i; cout << "{"; for (i = 0; i < len; ++i) { cout << ' ' << arr[i]; } cout << " }\n"; } // recursively permute the array arr, whose length is len. This recurses // the items from offset through len. It works by exchanging the item // at offset with each item after it, and then recursively permuting // from offset+1. static void recursivePermute(int arr[], int len, int offset) { // This works recursively by swapping the item at offset // with each item after it, and then recursively permuting // the items after the offset. if (offset >= len-1) { // This is the base case processResult(arr, len); } else { // First, just permute everything to the right. recursivePermute(arr, len, offset+1); int orig = arr[offset]; // remember the original value at offset int i; // Now, for every item to the right of offset, exchange it with the // item at offset and the permute everything to the right. for (i=offset+1; i < len; ++i) { arr[offset] = arr[i]; // swap the i'th element with the element at offset arr[i] = orig; recursivePermute(arr, len, offset+1); // recurse arr[i] = arr[offset]; // restore original value } arr[offset] = orig; } } // Process all permutations of the array. static void permute( int arr[], int len) { recursivePermute(arr, len, 0); } ```

 Re: Question about a "combinations" algorithm Message #10 Posted by Gilles Carpentier on 20 Sept 2012, 4:51 p.m.,in response to message #1 by Namir Hi Namir, if I understand well your problem, here is a 39gII program : ```EXPORT Perm(k,s) BEGIN LOCAL a,b,j; FOR j FROM 2 TO SIZE(s) DO a:=(k MOD j)+1; b:=s(a); s(a):=s(j); s(j):=b; k:=iquo(k,j); END; s; END; ``` Usage : Perm(5,{"a","b","c","d"}) Return the 5th permutation of the set. -> {"d","b","c",a"} As there are SIZE(s)! possible permutations,this program displays all the possible permutations ``` EXPORT PermAll(s) BEGIN LOCAL j; FOR j FROM 1 TO SIZE(s)! DO PRINT(Perm(j,s)); END END; ``` With 6 elements in the list, there is 720 permutations Of course the list may contain numbers (or matrix, or others list etc.) PS for TIM : A SWAP command would be welcome on the 39gII ;) a:=(k MOD j)+1; b:=s(a); s(a):=s(j); s(j):=b; -> SWAP(s((k MOD j)+1),s(j)); PS : I realise that perhaps you also want solutions like : { "a" } {"a" ,"b" } with {"a","b","c","d"} input ?? Edited: 20 Sept 2012, 6:02 p.m.

Go back to the main exhibit hall