CombinatorialCase110

From NARS2000
Jump to navigationJump to search

This case produces M-Permutations of N items (also called Partial Permutations or Sequences Without Repetition), where when M=N produces the familiar permutations !N. The length of each permutation returned is always M.

  • M labeled balls (1), N labeled boxes (1), at most one ball per box (0)
  • Sensitive to ⎕IO
  • Allows Lexicographic and Gray Code order
  • Counted result is an integer scalar
  • Generated result is an integer matrix.

The count for this function is !⍠(-M) N where !⍠(M) N calculates the Rising and Falling Factorial.

For example:

If we have 3 labeled balls (❶❷❸) and 3 labeled boxes (123) with at most one ball per box, there are 6 (↔ (!⍠¯3)3 ↔ 3×2×1) ways to meet these criteria:

1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3

The diagram above corresponds to

      110 1‼3 ⍝ Permutations in unspecified order
1 2 3
1 3 2
3 1 2
3 2 1
2 3 1
2 1 3
      110 2‼3 ⍝ Permutations in Lexicographic order when L=R
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
      110 3‼3 ⍝ Permutations in Gray Code order when L=R
1 2 3
1 3 2
3 1 2
3 2 1
2 3 1
2 1 3
      ⍝ Permutations of length M of N items
      ⍝ Labeled balls & boxes, ≤1 # Balls per Box
      !3
6
      110‼3 3
6
      110 0‼3 3
6
      ⍴110 1‼3 3
6 3
      110 1‼3 3
1 2 3
1 3 2
3 1 2
3 2 1
2 3 1
2 1 3
      110 1‼2 3
1 2
2 1
2 3
3 2
1 3
3 1
      110 2‼2 3 ⍝ Lexicographic order for Permutations with L≠R not implemented as yet
NONCE ERROR
      110 2‼2 3
           ∧
      110 3‼2 3 ⍝ Gray Code order for Permutations with L≠R not implemented as yet
NONCE ERROR
      110 3‼2 3
           ∧
      110 1‼1 3
1
2
3

A function to calculate the permutations of M items could be defined as

      perm←{110 1‼⍵}