0

Consider the following list:

elems = ('banana', 'apple', 'orange', 'melon')

I need to define a function that assigns a unique integer to each ordered combination of one to three non-repeated elements. For example:

banana                --> 1
banana, apple         --> 2
banana, orange        --> 3
banana, melon         --> 4
banana, apple, orange --> 5
banana, apple, melon  --> 6
banana, orange, apple --> 7
banana, orange, melon --> 8
banana, melon, apple  --> 9
banana, melon, orange --> 10
apple                 --> 11
apple, banana         --> 12
apple, orange         --> 13
...

My actual list contains more than 20 elements so defining the entire set of combinations manually is not possible. The function would take as input a minimum of one and a maximum of three elements, and return the unique integer associated with them, following the above convention.

I've been playing around with itertools.combinations() and itertools.combinations_with_replacement() but they don't return what I need.

Gabriel
  • 40,504
  • 73
  • 230
  • 404
  • The `itertools` functions would only help if you were iterating over all combinations/permutations/etc. For what you're doing, you need to determine the index based on the values(s). I'd just do the math. First determine how many one, two, and three element sequences. Then, depending on the number of elements, add the previous counts as an offset. That reduces the problem to handing a fixed number of elements. Then do the same thing: determine the index of the first element, then determine the number you need to skip past, etc. It's a little tedious, but simple. – Tom Karzes Sep 07 '21 at 13:43
  • could you please share the code you have tried so far? – Sabil Sep 07 '21 at 13:43
  • I thought about that too Tom, I was just hoping that there was already a simple approach baked into ìtertools`. Thank you! – Gabriel Sep 07 '21 at 13:59

1 Answers1

2

Well, given the powerset of the elements, e.g. from the answers to this question:

How to get all subsets of a set? (powerset)

It seems like what you want is all the permutations of the elements of the powerset, right?

list(enumerate([p for s in powerset(elems) for p in permutations(s)]))
# => [(0, ()), (1, ('banana',)), (2, ('apple',)), (3, ('orange',)), 
(4, ('melon',)), (5, ('banana', 'apple')), (6, ('apple', 'banana')), 
(7, ('banana', 'orange')), (8, ('orange', 'banana')), 
(9, ('banana', 'melon')), (10, ('melon', 'banana')),
(11, ('apple', 'orange')), (12, ('orange', 'apple')), 
(13, ('apple', 'melon')), (14, ('melon', 'apple')), 
(15, ('orange', 'melon')), (16, ('melon', 'orange')), 
(17, ('banana', 'apple', 'orange')), [...] 
(64, ('melon', 'orange', 'apple', 'banana'))]

You can run it through sorted before enumerating to get them in a different order; with no custom key or comparison func it will order the sequences such that all the ones starting with apple come first, then all the ones starting with banana, and so on..)

Mark Reed
  • 91,912
  • 16
  • 138
  • 175
  • 1
    This answer *almost* works as expected. The ordering obtained with `sorted()` is not exactly the one in the question, but it is close enough. Thank you Mark! – Gabriel Sep 07 '21 at 13:57