# All permutations of N numbers with at least K-different positions

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.

• 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? – Yuval Filmus May 29 '18 at 6:26
• 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. – flybynight May 29 '18 at 7:26
• 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? – Yuval Filmus May 29 '18 at 8:00
• Yes, exactly, the maximum size solution starting form the identity permutation. – flybynight May 30 '18 at 10:16
• The exact answer is likely unknown in general, and hard to find computationally. Look up permutation codes. – Yuval Filmus May 30 '18 at 11:30