1
$\begingroup$

I'm trying to generate all permutations of N numbers where any two permutations are different by at least K positions. I would just like a push in the right direction, the trivial method of memorizing every valid permutation and then just comparing at each step would be impractical for large values of N.

Example:

N=4, K=3

1 2 3 4 - good

1 2 4 3 - skip, only 2 positions differ from the first permutation

1 3 2 4 - skip, only 2 positions differ from the first permutation

1 3 4 2 - good

1 4 2 3 - good

1 4 3 2 - skip, only 2 positions differ from the last permutation

and so on

Any help is highly appreciated. Thank you.

$\endgroup$
  • $\begingroup$ I don't understand your goal. Are you trying to find a collection of permutations on $N$ points, any two of which differ in at least $K$ positions? There are many such collections. Which one are you interested in? $\endgroup$ – Yuval Filmus May 29 '18 at 6:26
  • $\begingroup$ Yes that is exactly what I'm looking for. I'm aware that there are many solutions depending on the order you choose to generate permutations, but I'm just interested in a way to generate just one of them starting from 1,2, ... n. $\endgroup$ – flybynight May 29 '18 at 7:26
  • $\begingroup$ One solution is the empty set. Another is just the identity permutation. And so on. Are you interested in a maximal solution, i.e. one to which no permutation can be added? A maximum size solution? $\endgroup$ – Yuval Filmus May 29 '18 at 8:00
  • $\begingroup$ Yes, exactly, the maximum size solution starting form the identity permutation. $\endgroup$ – flybynight May 30 '18 at 10:16
  • $\begingroup$ The exact answer is likely unknown in general, and hard to find computationally. Look up permutation codes. $\endgroup$ – Yuval Filmus May 30 '18 at 11:30

Your Answer

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

Browse other questions tagged or ask your own question.