Question about a "combinations" algorithm « Next Oldest | Next Newest »

 ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 09-19-2012, 04:32 PM 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. ▼ Kiyoshi Akima Senior Member Posts: 325 Threads: 18 Joined: Jul 2006 09-19-2012, 04:47 PM Brute-force C/C++: ```{ int a; for (a = 1; a <= 10; a++) for (a = a; a <= 10; a++) for (a = a; a <= 10; a++) for (a = a; a <= 10; a++) for (a = a; a <= 10; a++) for (a = a; a <= 10; a++) { // do whatever } } ``` ▼ Kiyoshi Akima Senior Member Posts: 325 Threads: 18 Joined: Jul 2006 09-19-2012, 04:49 PM 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? ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 09-19-2012, 08:06 PM 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. Marcel Samek Member Posts: 189 Threads: 39 Joined: Nov 2011 09-19-2012, 04:57 PM Just to make the question perfectly clear: 1) Are you talking about combinations or permutations 2) Is repetition of elements allowed? M. ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 09-19-2012, 08:06 PM Yes you can repeat the elements, Paul Dale Posting Freak Posts: 3,229 Threads: 42 Joined: Jul 2006 09-19-2012, 05:19 PM 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 Marcus von Cube, Germany Posting Freak Posts: 3,283 Threads: 104 Joined: Jul 2005 09-20-2012, 02:30 PM 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. David Hayden Senior Member Posts: 528 Threads: 40 Joined: Dec 2008 09-20-2012, 03:31 PM 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); } ``` Gilles Carpentier Senior Member Posts: 468 Threads: 17 Joined: May 2011 09-20-2012, 04:51 PM 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.

 Possibly Related Threads... Thread Author Replies Views Last Post combinations of k bits wp34s Andrew Nikitin 11 1,557 09-02-2013, 07:32 PM Last Post: mjcohen Linear Programming - Simplex Algorithm LarryLion 5 915 09-04-2012, 10:57 PM Last Post: David Hayden Algorithm for fitting a logistic curve? Tim Wessman 5 827 11-13-2011, 01:22 AM Last Post: Wes Loewer A fast and compact algorithm for the normal quantile Dieter 13 1,659 04-22-2011, 07:11 PM Last Post: Paul Dale The forensics algorithm for the 10s Palmer O. Hanson, Jr. 4 710 01-19-2010, 11:25 PM Last Post: Katie Wasserman An old logrithm algorithm Palmer O. Hanson, Jr. 8 1,098 12-26-2008, 10:47 PM Last Post: PatrickS Calculator Algorithm or Canon F-766S vs TI-89 Joerg Woerner 7 988 06-04-2008, 10:54 AM Last Post: Gunnar Degnbol CORDIC Trigonometric Algorithm on an HP17BII Charles 4 801 03-14-2008, 12:14 AM Last Post: Eric Smith HP-16C Encryption Algorithm John Williamson 3 649 01-19-2006, 05:45 AM Last Post: John Williamson New root-seeking algorithm Namir 7 1,054 12-10-2005, 10:39 PM Last Post: Namir

Forum Jump: 