Question about a "combinations" algorithm

[Namir]

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]

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

          }

}

[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?

[Namir]

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]

Just to make the question perfectly clear:

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

M.

[Namir]

Yes you can repeat the elements,

[Paul Dale]

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

[Marcus von Cube, Germany]

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]

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]

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.