Stream all unordered/shuffled unique permutation of elements in a nested list (list of list) in Python?

Question

I have two-level nested list like following.

[[0, 1], [2], [3, 4], [5, 5], [6], [7], [8], [9], [10, 11], [12]]

I want to generate all 8 unique permutations of this nested list, but my application absolutely needs the output to be (pseudo-)randomized and unordered. Usually, permutation strategies produce the permutations in order, but I want to be able to produce all permutations out of order.

Moreover, this MUST be done through some generator, as the nested list can be very long, and number of unique permutations can explode combinatorially.

Case in point, the following output is desired for the above list.

(0, 2, 3, 5, 6, 7, 8, 9, 10, 12)
(1, 2, 3, 5, 6, 7, 8, 9, 10, 12)
(0, 2, 3, 5, 6, 7, 8, 9, 11, 12)
(1, 2, 4, 5, 6, 7, 8, 9, 10, 12)
(0, 2, 4, 5, 6, 7, 8, 9, 10, 12)
(1, 2, 3, 5, 6, 7, 8, 9, 11, 12)
(1, 2, 4, 5, 6, 7, 8, 9, 11, 12)
(0, 2, 4, 5, 6, 7, 8, 9, 11, 12)

...as opposed to the following, which is generated by itertools.product(*some_list):

(0, 2, 3, 5, 6, 7, 8, 9, 11, 12)
(0, 2, 3, 5, 6, 7, 8, 9, 10, 12)
(0, 2, 3, 5, 6, 7, 8, 9, 11, 12)
(0, 2, 3, 5, 6, 7, 8, 9, 10, 12)
(0, 2, 4, 5, 6, 7, 8, 9, 11, 12)
(0, 2, 4, 5, 6, 7, 8, 9, 10, 12)
(0, 2, 4, 5, 6, 7, 8, 9, 11, 12)
(0, 2, 4, 5, 6, 7, 8, 9, 10, 12)
(1, 2, 3, 5, 6, 7, 8, 9, 11, 12)
(1, 2, 3, 5, 6, 7, 8, 9, 10, 12)
(1, 2, 3, 5, 6, 7, 8, 9, 11, 12)
(1, 2, 3, 5, 6, 7, 8, 9, 10, 12)
(1, 2, 4, 5, 6, 7, 8, 9, 11, 12)
(1, 2, 4, 5, 6, 7, 8, 9, 10, 12)
(1, 2, 4, 5, 6, 7, 8, 9, 11, 12)
(1, 2, 4, 5, 6, 7, 8, 9, 10, 12)

Even some solution that does exactly what itertools.product does, but generates permutations out of order will help me a lot. Any help is appreciated.

The following code illustrates my existing approach.

def perm_attempt():
    meta_seq = [[0, 1], [2], [3, 4], [5, 5], [6], [7], [8], [9], [10, 11], [12]]
    print meta_seq
    iter_count = np.prod([len(set(x)) for x in meta_seq])
    print iter_count
    print
    set_l = set()
    for _ in xrange(iter_count*10):
        l = [np.random.choice(x) for x in meta_seq]
        # print l
        set_l.add(tuple(l))
    print
    print len(set_l)
    print
    # for s in set_l:
    #     print s

Well, even then, product generates the permutation in order. I need the output to be **strictly** unordered or shuffled, while storing nothing in memory. A streaming solution if you will. — neo4k, Aug 04 '17 at 02:40
It's hard to see how you could ensure the outputs are unique, while storing nothing in memory. Because if you neither store what you've already produced, nor determine in advance the order in which you will produce outputs, how do you avoid duplicates? — perigon, Aug 04 '17 at 02:45
http://www.cut-the-knot.org/Curriculum/Combinatorics/JohnsonTrotter.shtml — cs95, Aug 04 '17 at 02:46
...why do you want to generate those words? And do you mean actual words in some real human language, or just arbitrary sequences of letters like jepxi? If you mean actual words, you'd be better off shuffling a wordlist. — user2357112, Aug 04 '17 at 02:47
These are not actual words, these are all words generated from a user-defined alphabet set. The user needs to generate at least some if not all of the unique permutations, but they must be unordered. — neo4k, Aug 04 '17 at 02:51
@perigon Well if some approximate bounds are possible, I can deal with it, I guess. Like possibility of duplicates would be some x% of times, maybe... But, ideally, I am looking for something that does what product does, but not in order. Even that itself would go a long way to solve this problem. — neo4k, Aug 04 '17 at 02:56
Yes, if duplicates are allowed, then you can use a random integer generator to index into each of the sub lists. This will generate permutations randomly as well as be streaming (on demand you can ask for a new permutation), but there may be some duplicates. — crazyGamer, Aug 04 '17 at 02:58
Yep. To make this solution work without duplicates, you can store a set of the generated indices you've used each time, and compare against that. It'll still be some storage, but proportional to the number you've generated already rather than to the total number of possibilities. — perigon, Aug 04 '17 at 02:59
That is what I am doing right now. random.shuffle on each sublist, followed by picking the last element in the sublist. When the final list is generated, I am checking against the set of all previously generated string. But isn't a more elegant solution possible? — neo4k, Aug 04 '17 at 03:03
For finding bounds, see here: https://stats.stackexchange.com/questions/57347/expected-number-of-duplicates-triplicates-etc-when-drawing-with-replacement — perigon, Aug 04 '17 at 03:03
Also, see here, particularly the LFSR answer (if you don't need "real" randomness): https://stackoverflow.com/questions/4040001/creating-random-numbers-with-no-duplicates — perigon, Aug 04 '17 at 03:13
I do not need real randomness. Just out of order sampling of the entire unique permutation space. — neo4k, Aug 04 '17 at 03:17
I see the code, try out my answer below: basically replace the for loops with those two lines of code. Let me know if it helps your case. — crazyGamer, Aug 04 '17 at 03:18
How random do you need them to do? LCGs aren't that random, but can be used to generate the indices of permutations without needing to store the previously generated indices. Then, these indices can be backtracked to find the corresponding permutation. — Jared Goguen, Aug 04 '17 at 20:29
Any manner of pseudo-randomness is fine. Could you illustrate your comment in an answer? Thanks. — neo4k, Aug 04 '17 at 20:32
Is it okay if the 8 permutations come out in the same order every time, or do you want the randomness to be "seedable"? — user2357112, Aug 04 '17 at 21:31
The techniques of [format-preserving encryption](https://en.wikipedia.org/wiki/Format-preserving_encryption) may be useful for generating a random permutation of the integers from 1 up to the total number of outputs, as a stream. From there, converting an integer to the output it specifies is fairly straightforward. — user2357112, Aug 04 '17 at 21:35

Gustavo Bezerra · Accepted Answer · 2017-08-04T03:07:50.533

You can try iterating over the following generator:

def random_perm(l):
    while True:
        yield [random.choice(sublist) for sublist in l]

Sample usage:

l = [[0, 1], [2], [3, 4], [5, 5], [6], [7], [8], [9], [10, 11], [12]]
g = random_perm(l)
for _ in range(10):
    print(next(g))

Output:

[0, 2, 4, 5, 6, 7, 8, 9, 10, 12]
[1, 2, 4, 5, 6, 7, 8, 9, 11, 12]
[0, 2, 3, 5, 6, 7, 8, 9, 10, 12]
[0, 2, 3, 5, 6, 7, 8, 9, 10, 12]
[0, 2, 3, 5, 6, 7, 8, 9, 11, 12]
[1, 2, 4, 5, 6, 7, 8, 9, 10, 12]
[0, 2, 3, 5, 6, 7, 8, 9, 11, 12]
[1, 2, 4, 5, 6, 7, 8, 9, 11, 12]
[1, 2, 4, 5, 6, 7, 8, 9, 10, 12]
[0, 2, 4, 5, 6, 7, 8, 9, 10, 12]

However, as others have pointed out in the comments, unless you cache the yield results in memory somehow, you can't really guarantee you won't get duplicates. You are also not guaranteed to get all 8 unique iterations in any 8 consecutive iterations.

Thanks, I am doing something similar already. As you see, I need to iterate more than possible number of unique sequences in order to find all unique permutations out of order. This can be an issue when dealing with a large nested list, having billions of unique possible permutations. — neo4k, Aug 04 '17 at 03:07

score 0 · Answer 2 · answered Aug 04 '17 at 03:11

0

If memory will not be a problem, you can try the following:

permList = itertools.product(*list_of_lists)
randomPermList = numpy.random.permutation(list(permList))

This is unique and random, but will not be an iteration.

answered Aug 04 '17 at 03:11

crazyGamer

1,119
9
16

Memory is definitely a problem. – neo4k Aug 04 '17 at 03:16
As you are storing every permutation in a set, aren't you going to use the same memory anyway? Could you clarify this please? – crazyGamer Aug 04 '17 at 03:21
@crazyGamer OP mentioned **this MUST be done through some generator**. So this is not a valid solution. – Alex Fung Aug 04 '17 at 03:22
@crazyGamer I am storing the permutation in a set as of now, but that is not my end goal. I wanna be able to stream unordered permutations. – neo4k Aug 04 '17 at 04:03

score 0 · Answer 3 · answered Aug 04 '17 at 03:18

0

A little cleaner than your current solution:

meta_seq = [[0, 1], [2], [3, 4], [5, 5], [6], [7], [8], [9], [10, 11], [12]]
print meta_seq
iter_count = np.prod([len(set(x)) for x in meta_seq])
print iter_count
print
set_l = set()
for _ in xrange(iter_count*100):
    choices = tuple([np.random.choice(sub_seq) for sub_seq in meta_seq])
    if not choices in set_l:
        set_l.add(choices)
        print choices
print
print len(set_l)
print

answered Aug 04 '17 at 03:18

perigon

2,160
11
16

Incorporated your suggestion, sure is better than shuffle+last_element. – neo4k Aug 04 '17 at 04:13

Stream all unordered/shuffled unique permutation of elements in a nested list (list of list) in Python?

3 Answers3

Linked