2
$\begingroup$

Say I have a shuffled list that was shuffled in Python using random.shuffle(). The shuffling was performed using a seeded random number generator. Is there a way I can get the original list back, i.e. un-shuffle the list? eg list1=[1,4,2,5] after seeding random and shuffling list2=[5,2,1,4] is there a way to get back list1 if we only have knowledge of list2 and seed value

$\endgroup$
  • $\begingroup$ Do you keep the seed or not? $\endgroup$ – kelalaka Mar 19 at 22:56
  • $\begingroup$ This site is not about implementation questions and Python specific questions are off topic. I've slightly changed the question so it is more generic. Beware that requiring a Python implementation will make this question off topic. $\endgroup$ – Maarten Bodewes Mar 19 at 23:59
  • $\begingroup$ @kelalaka yes i do $\endgroup$ – Dhaval Patel Mar 25 at 22:36
3
$\begingroup$

Yes. Throughout this, I will make the assumption (which appears to be the case) that random.shuffle() permutes the list in a way that only depends on:

  • The seed used
  • The length of the list being shuffled

This is to say that, for a fixed seed and fixed length of a list (say $n$), random.shuffle() chooses some permutation $\sigma\in S_n$, and then sends the list:

$$[a_1,a_2,\dots, a_n] \mapsto [a_{\sigma(1)}, a_{\sigma(2)},\dots, a_{\sigma(n)}]$$

For example, if $n = 4$, and $\sigma$ sends $1 \to 2$, $2\to 4$, $3\to 3$, and $4\to 1$, then for any initial list $[a_1, a_2, a_3, a_4]$, random.shuffle() will permute it to $[a_{\sigma(1)}, a_{\sigma(2)},\dots, a_{\sigma(n)}] = [a_2, a_4, a_3, a_1]$.

Let $ls = [a_1,\dots, a_n]$ be the (initial) list you care about, and let $\sigma(ls) = [a_{\sigma(1)},\dots, a_{\sigma(n)}]$ be the shuffled version of it. We can "unshuffled" it by using our prior assumption about random.shuffle() to "find" the permutation $\sigma$ that was used before. In particular, if we set the seed the same, and use a list $\mathsf{perm} = [b_1,\dots, b_n]$ of the same length, we'll have that:

$$\sigma(\mathsf{perm}) = [b_{\sigma(1)}, b_{\sigma(2)},\dots, b_{\sigma(n)}]$$ Then, if we have some way of restoring $\sigma(\mathsf{perm})\mapsto \mathsf{perm}$, we can simply "do these same steps" to $\sigma(ls)$ to recover $ls$.

Because of this, a particularly easy choice of $\mathsf{perm}$ to work with is $\mathsf{perm}= [1,2,\dots,n]$ (we can return to it via sorting). Note in that $b_i = i$, so $\sigma(\mathsf{perm}) = [\sigma(1),\dots, \sigma(n)]$.

One particularly easy way to "sort $\sigma(\mathsf{perm})$, but apply the same sequence of transpositions to $\sigma(ls)$" is by creating the "zipped list":

$$\mathsf{zipped\_list} = [(\sigma(ls)[0], \sigma(\mathsf{perm})[0]), (\sigma(ls)[1], \sigma(\mathsf{perm})[1]), \dots, (\sigma(ls)[n], \sigma(\mathsf{perm})[n])]$$

Note that each part of each tuple has been permuted precisely the same way! So we can view this as: $$\sigma([(a_1, 1), (a_2, 2), \dots, (a_n, n)])$$ I.e. our initial list, along with the list $[1,2,\dots,n]$, with the same permutation applied to both of them. We can then remove this permutation by sorting this larger list based on the second component of each tuple. This will return the list $\sigma([1,2,\dots,n])$ to $[1,2,\dots,n]$, and will therefore return $\sigma([a_1,\dots,a_n])$ to $[a_1,\dots, a_n]$ as well (as the same sequence of moves, which "cancel out" $\sigma$, are being applied to each list).

In case this theoretical description of what's happening is still not clear, the following python3 code should demonstrate that this works. I've additionally uploaded it to an online interpreter here.

import random

def shuffle_under_seed(ls, seed):
  # Shuffle the list ls using the seed `seed`
  random.seed(seed)
  random.shuffle(ls)
  return ls

def unshuffle_list(shuffled_ls, seed):
  n = len(shuffled_ls)
  # Perm is [1, 2, ..., n]
  perm = [i for i in range(1, n + 1)]
  # Apply sigma to perm
  shuffled_perm = shuffle_under_seed(perm, seed)
  # Zip and unshuffle
  zipped_ls = list(zip(shuffled_ls, shuffled_perm))
  ls.sort(key=lambda x: x[1])
  return [a for (a, b) in ls]

These should satisfy, for any list ls, and any choice of seed, that unshuffle_ls(shuffled_under_seed(ls, seed), seed) == ls, which you can experimentally validate.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Beware that any functional changes to the random number generator may result in an invalid result. $\endgroup$ – Maarten Bodewes Mar 19 at 23:58
  • $\begingroup$ thank you for the time to explain this but, my question is that is there a way to reverse the process of shuffling if we don't have the original list. eg list1=[1,4,2,5] after seeding random and shuffling list2=[5,2,1,4] is there a way to get back list1 if we only have knowledge of list2 and seed value $\endgroup$ – Dhaval Patel Mar 25 at 22:32
  • $\begingroup$ @DhavalPatel The answer is yes, as my previous answer spelled out. As I'm unsure what your conceptual difficulty is, I've tried to flesh out the explanation, and have included python code which does "unshuffle" the list as a concrete demonstration that this works. $\endgroup$ – Mark Mar 25 at 23:21
  • $\begingroup$ @mark Thank you, I now understand how it functions. I would like to thank everyone for answering my question $\endgroup$ – Dhaval Patel Mar 26 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.