4

I'm trying to generate all n-item combinations of a list of numbers while maintaining numerical order. So for example, if the list were

[1,2,3,4]

The ordered combinations of length 3 would be:

[1,2,3]
[2,3,4]
[1,2,4]
[1,3,4]

To be clear, I have to maintain numerical order, so [1,4,2] would not be a desired outcome.

Is there a function that does this, or a fast algorithm that would get it done? The actual list is 111 and I will be choosing 100 items. Thanks.

TomR
  • 546
  • 8
  • 19
  • You used the word combination, but you described permutation (permutations retain order). Can you clarify? – user590028 Sep 03 '14 at 18:12
  • 1
    Permutation means that order matters, but it doesn't retain numerical order, so it will also produce [2,4,1] from the list above, which is not what I need. – TomR Sep 03 '14 at 18:24
  • 1
    [How to get all combinations of length n in python](https://stackoverflow.com/questions/27974126/how-to-get-all-combinations-of-length-n-in-python) – Giorgos Xou Sep 19 '22 at 04:08
  • "The actual list is 111 and I will be choosing 100 items." Just to make sure, you understand that there are almost half a quadrillion such combinations? – Karl Knechtel Feb 28 '23 at 21:06

1 Answers1

6

Are you just looking for all the combinations of a given list of length n? If so you can just use combinations from itertools. Either way you'll probably want to go with itertools.

from itertools import combinations

numbers = [1,2,3,4]
for item in combinations(numbers, 3):
    print sorted(item)
user590028
  • 11,364
  • 3
  • 40
  • 57
  • I'm not sure if he wants permutation or combination? If it turns out OP wanted combinations, I'll remove my post. – user590028 Sep 03 '14 at 18:11
  • 4
    @user590028 Yeah, I originally thought permutations but when I saw the expected output it pointed towards combinations. However I think what he wants is combinations while preserving the order that they appear in the list. For example you can have [1,3,4] but not [3,1,4]. –  Sep 03 '14 at 18:13
  • 2
    Thimble is correct. I want combinations while preserving order, which is why neither the pure combination or permutation functions from itertools do what I need. – TomR Sep 03 '14 at 18:23
  • @TomR that depends on how you would define order. In your example you show [2,3,4] being before [1,2,4]. Normal conventions would have that being at the bottom. You would need to define what order you want. Combinations automatically ordered them starting with the first index and moving forward. –  Sep 03 '14 at 18:30
  • 1
    Thimble had the right answer (so I removed my permutations answer). All he needed todo was sort the result. I've edited his answer to reflect your needs – user590028 Sep 03 '14 at 18:36
  • That works. I don't care at all about the order of the combinations, just that the combinations themselves are ordered. Thimble's answer is perfect. – TomR Sep 03 '14 at 18:41