The Museum of HP Calculators

HP Forum Archive 21

[ Return to Index | Top of Index ]

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

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.

[ Return to Index | Top of Index ]

Go back to the main exhibit hall