Generate every permutation of the tail, then insert its missing head at every possible position. The helper preserves order among the elements already present:
sml
fun insertEverywhere x [] = [[x]]
  | insertEverywhere x (y :: ys) =
      (x :: y :: ys) ::
      List.map (fn zs => y :: zs) (insertEverywhere x ys);

fun permutations [] = [[]]
  | permutations (x :: xs) =
      List.concat
        (List.map (insertEverywhere x) (permutations xs));
The first helper result inserts before ; the mapped recursive results put back at the front and insert farther along. For a list of length , it yields exactly positions. The empty list has one permutation, itself, so the base result is [[]], not [].
For correctness, use structural induction. Any permutation of x :: xs has a unique position containing . Removing that position leaves a permutation of xs, supplied by the induction hypothesis; reinserting at its unique position reconstructs the required output. With distinct input elements, neither the tail permutation nor the insertion position can be duplicated, so each output occurs once. Consequently a length- input yields exactly permutations, in an unrestricted order. The explicit output is large; this is not a polynomial-time enumeration with respect to alone.

Ancestors (11)

  1. b
  2. 5
  3. Paper 5
  4. ia
  5. 2006
  6. Past exam of the mathematics course of the University of Cambridge
  7. Mathematics course of the University of Cambridge
  8. Course of the University of Cambridge
  9. University of Cambridge
  10. List of universities
  11. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version