How do I get all the orderings of a list so that the list is equal to another list?
I have lists A and B that may have duplicates, for example:
A = ['x', 'x', 7]
B = [7, 'x', 'x']
Now I want all index permutations to permute list B to list A:
[1, 2, 0] # because [B[1], B[2], B[0]] == A
[2, 1, 0] # because [B[2], B[1], B[0]] == A
Is there a way to achieve this without repeating all possible permutations? I am already using
import itertools
for p in itertools.permutations(range(len(B))):
if A == permute(B,p):
to iterate over all possible permutations and check the ones I want, but I want the ones I want faster.
source to share
Here's one way to do it. My function perms
generates all valid permutations. I first collect the indices for each element in B, then I recursively build and get the permutations, always choosing one of the available indices for each element in until the permutation is ready.
from collections import defaultdict
def perms(A, B):
indexes = defaultdict(set)
for i, e in enumerate(B):
indexes[e].add(i)
def find(perm):
k = len(perm)
if k == len(A):
yield perm
return
I = indexes[A[k]]
for i in list(I):
I.remove(i)
yield from find(perm + (i,))
I.add(i)
yield from find(())
Using:
A = ['x', 'x', 7]
B = [7, 'x', 'x']
for perm in perms(A, B):
print(perm)
Output:
(1, 2, 0) (2, 1, 0)
source to share
You have to break down your problem into two parts:
- first find a specific permutation
sigma_0
that mapsB
toA
- find the set of
S_B
all permutations that map B onto itself
Then the set you are looking for is simple {sigma_0 \circ \sigma, sigma \in S_B}
.
Now the question arises: how to determine S_B
? To do this, you can simply notice that if you write the set {0,1,2,..,n}
(s n=2
in your case) as A_1 \cup .. A_k
, where each A_i
matches the indices in B
that correspond to the i-th element (in your case, you would have A_1 = {1,2}
and A_2 = {0}
), then each element from S_B
can be written in a unique way as a piece tau_1 \circ .. tau_k
, where each tau_i
is a permutation acting on A_i
.
So, in your case S_B = {id, (1,2)}
, you can take sigma_0 = (0,2)
. It follows that you have a value set {(0,2), (2,0,1)}
.
source to share
You can do this in three steps. First, create a dictionary from list B that has elements as keys and indices as values. In your case, the dictionary for your list B:
B = [7, 'x', 'x']
7 - [0]
'x' - [1, 2]
Then go to your list A and create an index that maps the indices of List A to the corresponding indices of List B. That is:
A = ['x', 'x', 7]
0 - [1, 2]
1 - [1, 2]
2 - [0]
From this you can generate all valid mappings. It should be easy enough to write code that, given the above index, will generate [1, 2, 0]
and [2, 1, 0]
.
source to share
Here's something in Python. I have used strings for hashing since I am not familiar with how to pass sets and arrays as recursive arguments in Python, although they might be more efficient.
A = ['x', 'x', 7, 'y', 8, 8]
B = [7, 'x', 8, 'x', 8, 'y']
H = {}
# record the indexes of elements in B
for i in xrange(0,len(B)):
if B[i] in H:
H[ B[i] ].append(str(i))
else:
H[ B[i] ] = [str(i)]
# build permutations in the order that the elements are encountered in A
def perms(perm,i,visited,l):
if i==l:
print perm
return
for j in H[ A[i] ]:
if j not in visited:
perms(perm + j,i + 1,visited + j,l)
perms("",0,"",len(A))
Output:
130524 130542 310524 310542
source to share