What is an efficient algorithm to create all possible combinations?

Question

Let's say there's n amount of entries, each of whom can take the value of 0 or 1. That means there's 2^n possible combinations of those entries. The number of entries can vary from 1 to 6.

How can you create each possible combination as a sequence of numbers (i.e. for n = 2: 00, 01, 10, 11), without resorting to a thousand IFs?

Have you seen the answers to: http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n — Shog9, Aug 22 '09 at 19:14

score 17 · Accepted Answer · answered Aug 22 '09 at 19:14

17

You can achieve that just by printing the numbers 0..2^n-1 in binary form.

answered Aug 22 '09 at 19:14

Nick Dandoulakis

42,588
16
104
136

Thanks, didn't think of that. Sometimes the answer is right in front of your nose yet you don't see it. – Hans Aug 22 '09 at 20:07

score 3 · Answer 2 · edited May 23 '17 at 10:28

3

Might as well just use ints:

n = 5
for x in range(2**n):
  print ''.join(str((x>>i)&1) for i in xrange(n-1,-1,-1))

Crazy decimal to binary conversion lifted from this answer.

Output:

edited May 23 '17 at 10:28

Community

1
1

answered Aug 22 '09 at 19:21

I. J. Kennedy

24,725
16
62
87

Sadly I don't understand a bit of Python, I mainly use Java. But I'll try to give it a shot. Thanks. – Hans Aug 22 '09 at 20:08

score 1 · Answer 3 · answered Aug 22 '09 at 19:15

1

Generating the mth Lexicographical Element of a Mathematical Combination. LINK

And you must see this by DON KNUTH.(Generating all possible combinations.NOTE:C# code is also provide there.)

answered Aug 22 '09 at 19:15

Pratik Deoghare

35,497
30
100
146

score 0 · Answer 4 · answered Aug 22 '09 at 19:20

0

If possible values for each entries can be only 0 or 1, and you want just 0 and 1 combination, why don't you use the natural integers (in binary form) up to 2^(n-1)...as suggested above by Nick..and format those with '0' padding if you want string...

answered Aug 22 '09 at 19:20

mshsayem

17,557
11
61
69

score 0 · Answer 5 · answered May 02 '16 at 14:06

0

Or use itertools:

import itertools

for item in itertools.product((1, 0), repeat=4):
    print item

Note that the item is a tuple of 4 elements in this case.

answered May 02 '16 at 14:06

Gooey

4,740
10
42
76

What is an efficient algorithm to create all possible combinations?

5 Answers5