Question about a "combinations" algorithm



#11

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.


#12

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
}
}

#13

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?


#14

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.

#15

Just to make the question perfectly clear:

1) Are you talking about combinations or permutations
2) Is repetition of elements allowed?

M.


#16

Yes you can repeat the elements,

#17

C++ is easy. The standard template library include this algorithm.

        #include <algorithm>

Then call:

        next_permutation(array, array+n)
or prev_permutation(array, array+n)


The algorithm used is well known.


- Pauli

#18

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.

#19

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);
}

#20

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 3,253 09-02-2013, 07:32 PM
Last Post: mjcohen
  Linear Programming - Simplex Algorithm LarryLion 5 1,721 09-04-2012, 10:57 PM
Last Post: David Hayden
  Algorithm for fitting a logistic curve? Tim Wessman 5 1,828 11-13-2011, 01:22 AM
Last Post: Wes Loewer
  A fast and compact algorithm for the normal quantile Dieter 13 3,476 04-22-2011, 07:11 PM
Last Post: Paul Dale
  The forensics algorithm for the 10s Palmer O. Hanson, Jr. 4 1,516 01-19-2010, 11:25 PM
Last Post: Katie Wasserman
  An old logrithm algorithm Palmer O. Hanson, Jr. 8 2,215 12-26-2008, 10:47 PM
Last Post: PatrickS
  Calculator Algorithm or Canon F-766S vs TI-89 Joerg Woerner 7 2,095 06-04-2008, 10:54 AM
Last Post: Gunnar Degnbol
  CORDIC Trigonometric Algorithm on an HP17BII Charles 4 1,565 03-14-2008, 12:14 AM
Last Post: Eric Smith
  HP-16C Encryption Algorithm John Williamson 3 1,348 01-19-2006, 05:45 AM
Last Post: John Williamson
  New root-seeking algorithm Namir 7 2,336 12-10-2005, 10:39 PM
Last Post: Namir

Forum Jump: