What would be a good pseudo code or Python 3 code for the following permutations problem? Let us define a n-permutation as a bijective function $\pi: \{0,...,n-1\}\rightarrow \{0,...,n-1\} $ and represent it using a list, meaning that $\pi(i)=j $ iff list[i]=j. Let us also define a pair permutation as a permutation in which for every $ i\neq j , \thinspace \pi(i)=j \Leftrightarrow \pi(j)=i $ . I need to write a recursive function code, that takes an interger n, and generates all n-pair permutations (every permutation appears, and only once). [This question appeared on a test, that it's solution remains confidential :( ]

  • $\begingroup$ For the first element select en element which will be its pair (also, consider an option that an element will be unpaired, i.e. $\pi(i)=i$). For the first of the remaining elements, select an element which will be its pair. Repeat. By "select" I mean to consider all possible combinations, and by "repeat" - to make a recursive call. $\endgroup$ – Dmitry Aug 5 '20 at 18:34
  • $\begingroup$ en.wikipedia.org/wiki/Involution_(mathematics) $\endgroup$ – D.W. Aug 5 '20 at 23:52

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.