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

Parameters

Options

Description

Examples

References

Compatibility

Calling Sequence

Permute(L, r, opts)

Parameters

L

-

{posint,range(integer),list,Vector}; 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.

• 

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:

– 

a list or Vector;

– 

a positive integer is equivalent to a list of integers from 1 to L;

– 

a range of integers is equivalent to list of integers in that range.

• 

The optional r parameter specifies the size of the permutations.

• 

If a list or Vector contains non-integers, a transformation is used to map the permutation to the elements of l. Consequently, the iteration is somewhat slower.

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

withIterator:

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

PPermute4:

forpinPdoprintf%{}d ,pend 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.

NumberP

24

(1)

Generate all permutations of a list with a repeated element.

PPermute1,2,2,3:

forpinPdoprintf%{}d ,pend do

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

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 := `if`(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(`if`(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:

alphameticmaple*sim = modelica + model

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

combinat[permute]

Iterator