HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

How get the permutation of two lists but the elements of each list remain in the same order?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
sametheordereachelementsbutliststwogetremain

Problem

So if I have lst1 = [a, b] and lst2 = [x, y] the result would be:

[x, y, a, b]
[x, a, y, b]
[x, a, b, y]
[a, x, y, b]
[a, x, b, y]
[a, b, x, y]


I'm thinking about doing something recursive where I take the first element of a list, place it at the start, then recursively take the next element of that list and shift it through each position (and on each shift go through all remaining elements of that list).

But I'm wondering if there may be a nicer way to do this?

edit: Some more elaborate info here

Solution

Generate a string chi with len(lst1) 0s and len(lst2) 1s, e.g. for lst1 = [x, y] and lst2 = [a, b, c], you generate chi = [0, 0, 1, 1, 1]. Then you shuffle chi to obtain your "characteristic vector". This new list will dictate the order in which to output elements from lst1 and lst2.

I hope this Python program speaks for itself:

from random import shuffle

def permutation(lst1, lst2, chi):
    idx1 = 0
    idx2 = 0
    for i in range(len(lst1) + len(lst2)):
        if chi[i] == '0':
            yield lst1[idx1]
            idx1 += 1
        else:
            yield lst2[idx2]
            idx2 += 1

lst1 = 'xy'
lst2 = 'abc'

chi = list('0' * len(lst1) + '1' * len(lst2))
shuffle(chi)
print(''.join(chi))
print(''.join(list(permutation(lst1, lst2, chi))))


Outputs:

11001
abxyc

10011
axybc

00111
xyabc

Code Snippets

from random import shuffle

def permutation(lst1, lst2, chi):
    idx1 = 0
    idx2 = 0
    for i in range(len(lst1) + len(lst2)):
        if chi[i] == '0':
            yield lst1[idx1]
            idx1 += 1
        else:
            yield lst2[idx2]
            idx2 += 1

lst1 = 'xy'
lst2 = 'abc'

chi = list('0' * len(lst1) + '1' * len(lst2))
shuffle(chi)
print(''.join(chi))
print(''.join(list(permutation(lst1, lst2, chi))))
11001
abxyc

10011
axybc

00111
xyabc

Context

StackExchange Computer Science Q#104554, answer score: 3

Revisions (0)

No revisions yet.