Looking for a generic, fast, low-memory algorithm to output N-out-of-M combinations of an array without repetitions

Question

I have an array with players

$players = array('A','B','C','D','E','F');

and i want to get every possible 3 way finishing.

1st 2nd 3rd
A   B   C
A   B   D
...
C   A   B
C   B   A
...
F   D   E
F   E   D

I have some permutation algorithm but it must be something else since in permutation there is 6 * 5 * 4 * 3 * 2 * 1 combination and here is only 6 * 5 * 4

You say you have some permutation algorithm. If you want help with that I would suggest that you post the code for it. — Mizipzor, Jul 04 '12 at 14:00
The answer to your code, would be 6*5*4, as the rest of the places dont matter.. — BugFinder, Jul 04 '12 at 14:01
You guys do realize that he wants the permutations, not just the count, right?! — Shahbaz, Jul 04 '12 at 14:07

score 2 · Answer 1 · edited May 23 '17 at 11:48

2

Here's some pseudo-code to print your 3 out of 6 combinations without repetition:

for i = 1 to 6
  for j = 1 to 6
    if (j != i)
      for k = 1 to 6
        if (k != i && k != j)
          print(A[i], A[j], A[k])
        end if
      next k
    end if
  next j
next i

For the general k-of-n case see: Algorithm to return all combinations of k elements from n

edited May 23 '17 at 11:48

Community

1
1

answered Jul 04 '12 at 14:08

MicSim

26,265
16
90
133

1

And what if he wants 4 out of 7? Or 2 out of 5? Or 5 out of 10? Or 1 out of 4? Or 6 out of 6? Or 3 out of 8? Or 2 out of 4? Or 6 out of 8? Or 4 out of 5? – Shahbaz Jul 04 '12 at 14:10
Just adapt the code to it. The pseudo-code just addresses the given problem. No more, no less. – MicSim Jul 04 '12 at 14:11
1

What I mean is, even though this solves the specific problem, it doesn't at all scale and is not reusable under other circumstances. – Shahbaz Jul 04 '12 at 14:14
I completely agree. But why solve problems that maybe just don't exist? Changing the 6 to array length shoudn't be a problem. And it's stated quite clear in the question that he needs only 3 out of N (first 3 places of a competition). Else he could have asked the more generic question: "Looking for a generic, fast, low-memory footprint algorithm to output N-out-of-M combinations of an array without repetitions". ;-) – MicSim Jul 04 '12 at 14:21
2

he seems to have listened to your suggestion ;) – Shahbaz Jul 04 '12 at 14:30

score 1 · Answer 2 · answered Jul 04 '12 at 14:05

1

Given your permutation algorithm, you can use it in two steps to get the desired permutations.

First, let's consider the following mapping. Given input as A1 A2 A3 A4 A5 ... An, a value b1 b2 b3 b4 b5 ... bn means select Ai if bi is 1 and not if it is 0.

With your input, for example:

0 0 1 1 0 1 -> C D F
0 1 0 0 1 1 -> B E F

Now your algorithm can go as follows:

Take n as the number of elements (in your case 6) and m as the number you want to choose from.

Construct the following sequence:

0 0 0 ... 0 1 1 1 ... 1
\____ ____/ \____ ____/
     V           V
   n - m         m

Get all permutations of the above sequence and for each:
- Find the m elements that are marked in the sequence
- Get all permutations of those m elements and for each:
  - do whatever you want!

answered Jul 04 '12 at 14:05

Shahbaz

46,337
19
116
182

Im not 100% sure but as i figured out what i want is called combination and not permutation – user1435915 Jul 04 '12 at 14:21
1

In your example, `A B C` and `C A B` are distinguished. This is permutation. If you just want 3 of them, regardless of their order (combination), then you have to skip the inner `get_permutations`. – Shahbaz Jul 04 '12 at 14:29
It already exists in C++. It is called [`next_permutation`](http://www.sgi.com/tech/stl/next_permutation.html) – Shahbaz Jul 04 '12 at 18:32

barak1412 · Answer 3 · 2012-07-04T14:08:49.050

Your problem is not finding all permutations of 6 elements.

Your problem is to choose 3 elements, and than check its permutations.

The number of combinations = C(6,3)*3! = 6! / 3! = 6*5*4.

C(6,3) - for choosing 3 elements out of 6. (No matter the order)

3! - for ordering the 3 chosen elements.

This is the exactly number of combinations you should get. (and you do)

However, you can use your permutation algorithm to get all permutations of the 6 elements. Than, just ignore the last 3 elements, and remove duplicates from the result.

score 0 · Answer 4 · edited Jul 05 '12 at 12:44

I may be wrong but I think you have the correct amount of possible permutations here. You choose only 3 players among the 6 players array. So for the first player, you have 6 possibilities, for the second player you have 5 possibilities, and for the third player, you have 4 possibilities.

If you decide to have 4 players at the end instead of having 3, the possible amount of permutations would be 6*5*4*3, and so on.

I hope my math is not too old!

Looking for a generic, fast, low-memory algorithm to output N-out-of-M combinations of an array without repetitions

4 Answers4