Python itertools.product() get item index
Question: I have a given tuple `my_tuple` and I know it is in the return object of
itertools.product(). How could I find the index of `my_tuple` without
iterating over the itertools.product() object?

    
    
    import itertools
    permutations = itertools.product(my_sorted_list, repeat = perm_length)
    

Expected output similar of `any_list.index(interesting_pattern)`

**Edit** Note that I cannot use list() on the object because of memory
constraints

Using Python 2.7


Answer: You don't want to use `itertools.product` in this case. If you only want the
index, than you should calculate it with math.

Like others said before, this one is slow and needs a lot of memory:

    
    
    import itertools
    print list(itertools.product([0, 2, 3, 5], repeat=3)).index((3, 0, 2))
    

Much better is:

    
    
    def product_index(sorted_list, repeat, interesting_pattern):
        result = 0
        for index, number in enumerate(interesting_pattern):
            result += sorted_list.index(number) * len(sorted_list)**(repeat - 1 - index)
        return result
    
    print product_index([0, 2, 3, 5], 3, (3, 0, 2))
    

### Explanation:

Just look at the output of `list(itertools([0, 2, 3, 5], repeat=3))`:

    
    
    [(0, 0, 0), (0, 0, 2), (0, 0, 3), (0, 0, 5), (0, 2, 0), (0, 2, 2), (0, 2, 3), 
     (0, 2, 5), (0, 3, 0), (0, 3, 2), (0, 3, 3), (0, 3, 5), (0, 5, 0), (0, 5, 2), 
     (0, 5, 3), (0, 5, 5), (2, 0, 0), (2, 0, 2), (2, 0, 3), (2, 0, 5), (2, 2, 0), 
     (2, 2, 2), (2, 2, 3), (2, 2, 5), (2, 3, 0), (2, 3, 2), (2, 3, 3), (2, 3, 5), 
     (2, 5, 0), (2, 5, 2), (2, 5, 3), (2, 5, 5), (3, 0, 0), (3, 0, 2), (3, 0, 3), 
     (3, 0, 5), (3, 2, 0), (3, 2, 2), (3, 2, 3), (3, 2, 5), ...]
    

Since the input list is sorted, the generated tuples are also sorted. At first
`itertools.product` generates all tuples of length `3`, that start with `0`.
Then there are all tuples of length `3` that start with `2`. And so on.

So the algorithm goes through each element of `interesting_pattern` and
determines, how many of these tuples start with a number smaller.

So for `interesting_pattern = (3, 0, 2)` we have:

  * How many tuples of length `3` are there, where the first element is smaller than `3`? For the first element there are 2 possibilities (`0` and `2`) and all the other elements can be everything (4 possibilities). So there are `2*4*4 = 2*4^2 = 32`. Now we have the first digit 3, and only have to look at the subtuple `(0, 2)`. 
  * How many tuples of length `2` are there, where the first element is smaller than `0`? There is no possibility for the first element, but 4 possibilities for the second element, so `0*4 = 0*4^1 = 0`. 

  * And at last. How many tuples of length `1` are there, where the first element is smaller than `2`? There is 1 possibility for the first element (`0`), so `1 = 1*4^0 = 1`. 

In total we get `32 + 0 + 1 = 33`. The index is `33`.

### edit:

This algorithm is probably even faster, since you don't have to compute any
powers.

    
    
    def product_index2(sorted_list, interesting_pattern):
        result = 0
        for number in interesting_pattern:
            result = result * len(sorted_list) + sorted_list.index(number)
        return result
    

