Task

Write a program that generates all   permutations   of   n   different objects.   (Practically numerals!)



Related tasks
 
   Find the missing permutation
   Permutations/Derangements



 The number of samples of size k from n objects.


With   combinations and permutations   generation tasks. 






 Order Unimportant

 Order Important


 Without replacement








(


n
k


)




=

n



C

k


=



n
(
n
−
1
)
…
(
n
−
k
+
1
)


k
(
k
−
1
)
…
1





{\displaystyle {\binom {n}{k}}=^{n}\operatorname {C} _{k}={\frac {n(n-1)\ldots (n-k+1)}{k(k-1)\dots 1}}}










n



P

k


=
n
⋅
(
n
−
1
)
⋅
(
n
−
2
)
⋯
(
n
−
k
+
1
)


{\displaystyle ^{n}\operatorname {P} _{k}=n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)}




Task: Combinations

Task: Permutations


 With replacement








(



n
+
k
−
1

k


)




=

n
+
k
−
1



C

k


=



(
n
+
k
−
1
)
!


(
n
−
1
)
!
k
!





{\displaystyle {\binom {n+k-1}{k}}=^{n+k-1}\operatorname {C} _{k}={(n+k-1)! \over (n-1)!k!}}








n

k




{\displaystyle n^{k}}




Task: Combinations with repetitions

Task: Permutations with repetitions



/* NetRexx */
options replace format comments java crossref symbols nobinary
 
import java.util.List
import java.util.ArrayList
 
-- =============================================================================
/**
 * Permutation Iterator
 * <br />
 * <br />
 * Algorithm by E. W. Dijkstra, "A Discipline of Programming", Prentice-Hall, 1976, p.71
 */
class RPermutationIterator implements Iterator
 
  -- ---------------------------------------------------------------------------
  properties indirect
    perms = List
    permOrders = int[]
    maxN
    currentN
    first = boolean
 
  -- ---------------------------------------------------------------------------
  properties constant
    isTrue  = boolean (1 == 1)
    isFalse = boolean (1 \= 1)
 
  -- ---------------------------------------------------------------------------
  method RPermutationIterator(initial = List) public
    setUp(initial)
    return
 
  -- ---------------------------------------------------------------------------
  method RPermutationIterator(initial = Object[]) public
    init = ArrayList(initial.length)
    loop elmt over initial
      init.add(elmt)
      end elmt
    setUp(init)
    return
 
  -- ---------------------------------------------------------------------------
  method RPermutationIterator(initial = Rexx[]) public
    init = ArrayList(initial.length)
    loop elmt over initial
      init.add(elmt)
      end elmt
    setUp(init)
    return
 
  -- ---------------------------------------------------------------------------
  method setUp(initial = List) private
    setFirst(isTrue)
    setPerms(initial)
    setPermOrders(int[getPerms().size()])
    setMaxN(getPermOrders().length)
    setCurrentN(0)
    po = getPermOrders()
    loop i_ = 0 while i_ < po.length
      po[i_] = i_
      end i_
    return
 
  -- ---------------------------------------------------------------------------
  method hasNext() public returns boolean
    status = isTrue
    if getCurrentN() == factorial(getMaxN()) then status = isFalse
    setCurrentN(getCurrentN() + 1)    
    return status
 
  -- ---------------------------------------------------------------------------
  method next() public returns Object
    if isFirst() then setFirst(isFalse)
    else do
      po = getPermOrders()
      i_ = getMaxN() - 1
      loop while po[i_ - 1] >= po[i_]
        i_ = i_ - 1
        end
 
      j_ = getMaxN()
      loop while po[j_ - 1] <= po[i_ - 1]
        j_ = j_ - 1
        end
 
      swap(i_ - 1, j_ - 1)
 
      i_ = i_ + 1
      j_ = getMaxN()
      loop while i_ < j_
        swap(i_ - 1, j_ - 1)
        i_ = i_ + 1
        j_ = j_ - 1
        end
      end
    return reorder()
 
  -- ---------------------------------------------------------------------------
  method remove() public signals UnsupportedOperationException
    signal UnsupportedOperationException()
 
  -- ---------------------------------------------------------------------------
  method swap(i_, j_) private
    po = getPermOrders()
    save   = po[i_]
    po[i_] = po[j_]
    po[j_] = save
    return
 
  -- ---------------------------------------------------------------------------
  method reorder() private returns List
    result = ArrayList(getPerms().size())
    loop ix over getPermOrders()
      result.add(getPerms().get(ix))
      end ix
    return result
 
  -- ---------------------------------------------------------------------------
  /**
   * Calculate n factorial: {@code n! = 1 * 2 * 3 .. * n}
   * @param n
   * @return n!
   */
  method factorial(n) public static
    fact = 1
    if n > 1 then loop i = 1 while i <= n
      fact = fact * i
      end i
    return fact
 
  -- ---------------------------------------------------------------------------
  method main(args = String[]) public static
    thing02 = RPermutationIterator(['alpha', 'omega'])
    thing03 = RPermutationIterator([String 'one', 'two', 'three'])
    thing04 = RPermutationIterator(Arrays.asList([Integer(1), Integer(2), Integer(3), Integer(4)]))
    things = [thing02, thing03, thing04]
    loop thing over things
      N = thing.getMaxN()
      say 'Permutations:' N'! =' factorial(N)
      loop lineCount = 1 while thing.hasNext()
        prm = thing.next()
        say lineCount.right(8)':' prm.toString()
        end lineCount
      say 'Permutations:' N'! =' factorial(N)
      say
      end thing
    return
 