Iterator - Maple Programming Help

# Online Help

###### All Products    Maple    MapleSim

Home : Support : Online Help : Mathematics : Discrete Mathematics : Combinatorics : Iterator : Iterator/Permute

Iterator

 Permute
 generate permutations of a list

 Calling Sequence Permute(L, r, opts)

Parameters

 L - {posint,range(integer),list}; specifies elements to permute r - posint; (optional) size of permutations opts - (optional) equation(s) of the form option = value; specify options for the Permute command

Options

 • compile = truefalse
 True means compile the iterator. The default is true.
 • plain = truefalse
 True selects an algorithm that interchanges adjacent pairs of elements between each step.  Can only be used with full permutations of lists of distinct elements. The default is false.
 • rank = nonnegint
 Specify the starting rank of the iterator. The default is one. The starting rank reverts to one when the iterator is reset, reused, or copied.

Description

 • The Permute command returns an iterator that generates all permutations of the specified elements. The elements do not have to be distinct. A permutation of a list consists of all distinct arrangements of its elements.
 • The L parameter specifies the elements to permute. It may be
 – a list; if it contains any elements that are not of type integer[4], a transformation is used to map the permutation to the elements of L. Consequently, the iteration is somewhat slower.
 – a positive integer; the permuted list is the integers from 1 to L.
 – a range of integers; the permuted list is integers in that range.
 • The optional r parameter specifies the size of the permutations. The default is to permute the full list.

Methods

The iterator object has the following methods. The self parameter is the iterator object.

 • Number(self): return the number of iterations required to step through the iterator, assuming it started at rank one.
 • Rank(self,L): return the rank of the current iteration. Optionally pass L, a list or one-dimensional rtable, and return its rank.
 • Unrank(self,rnk): return a one-dimensional Array corresponding to the iterator output with rank rnk.

Examples

 > $\mathrm{with}\left(\mathrm{Iterator}\right):$

Create an iterator that generates all permutations of the integers 1 to 4.

 > $P≔\mathrm{Permute}\left(4\right):$
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}P\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{printf}\left("%\left\{\right\}d\n",p\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}$
 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1

Compute the number of iterations.

 > $\mathrm{Number}\left(P\right)$
 ${24}$ (1)

Generate all permutations of three elements from a list with a repeated element.

 > $P≔\mathrm{Permute}\left(\left[a,b,b,c\right],3\right):$
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}P\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{printf}\left("%\left\{\right\}a\n",p\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}$
 a b b a b c a c b b a b b a c b b a b b c b c a b c b c a b c b a c b b

Alphametics

An alphametic is a puzzle in which the user is given an arithmetic equation, with characters substituted for the digits.  The goal is to determine the digits which satisfy the equation.  The usual alphametic is a summation, or linear combination of words, however, a more general alphametic allows multiplication.

A brute-force solution of base-10 alphametics can be achieved in several seconds by iterating through all 10! permutations of the digits.  Here is a procedure, written as an appliable module, that uses the Permute constructor to do that.

 > alphametic := module() export ModuleApply; local SymbolToAlg;     ModuleApply := proc(eq :: string                         , base :: posint := 10                         , { compile :: truefalse := true }                         , \$                        )     local chars         , ex,i,n,vars,x,pred,iter         , p         ;     uses ST=StringTools;         # Parse the input string and convert an equation to an expression.         ex := parse(eq);         ex := ifelse(ex :: equation                      , (lhs-rhs)(ex)                      , ex                     );         # Extract the symbols (names).         vars := indets(ex,symbol);         # Convert each symbol in ex to an algebraic equivalent         # in terms of the characters in the the symbol.         ex := subs([seq(x = SymbolToAlg(x,base), x=vars)],ex);         # Assign vars the characters in ex         vars := indets(ex,symbol);         n := numelems(vars);         if n > base then             error "too many characters (%1) for base %2", n, base;         end if;         # Convert characters to indexed names of V         ex := subs([seq(vars[i]='V'[i],i=1..n)],ex);         ex := expand(ex);         # Assign a predicate that returns true if the permutation         # evaluates ex to 0 (evalb does not work in Compiler:-Compile).         pred := subs('_ex'=ex, proc(V :: Array(datatype=integer[4]))                                local ex := _ex;                                    if ex=0 then                                        return true;                                    else                                        return false;                                    end if;                                end proc                     );         # Optionally compile the predicate         if compile then             pred := Compiler:-Compile(pred);         end if;         # Construct an iterator to iterate over all permutations.         iter := Iterator:-Permute(0..(base-1),n                                   , _options['compile']                                  );         # Find solutions and format as equations.         vars := map(convert,vars,string);         chars := ST:-Explode(eq);         seq(ifelse(pred(p)                    , ST:-Join(subs([seq(vars[i]=convert(p[i],string), i = 1..n)]                                    , chars)                               ,"")                    , NULL)             , p=iter            );     end proc:     # Convert a symbol into a multinomial     # over the characters of the symbol.     SymbolToAlg := proc(symb,base::posint:=10)     local val,char;         val := 0;         for char in convert(symb,string) do             val := base*val+cat(,char);         end do;         val;     end proc: end module:

Solve the alphametic: maple*sim = modelica + model:

 > $\mathrm{alphametic}\left("maple*sim = modelica + model"\right)$
 ${"16540*781 = 12904836 + 12904"}$ (2)

References

 Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 2; generating all tuples and permutations, sec. 7.2.1.2, generating all permutations, pp. 39-44.
 ibid, Algorithm L, lexicographic permutation generation, p. 39.
 ibid, Algorithm T, plain change transitions, p. 43.
 ibid, Algorithm R, answer 9, p. 102.

Compatibility

 • The Iterator[Permute] command was introduced in Maple 2016.
 • For more information on Maple 2016 changes, see Updates in Maple 2016.

 See Also