Paste: unique permutations

USING: kernel make math math.ranges sequences ;
IN: unique-permutations

: should-swap? ( start curr seq -- ? )
    [ nipd nth ] [ <slice> member? not ] 3bi ;

:: unique-permutations, ( seq index n -- )
    index n >=
    [ seq clone , ] [
        index n [a..b) [| i |
            index i seq should-swap? [
                index i seq exchange seq index 1 +
                n unique-permutations, index i seq exchange
            ] when
        ] each
    ] if ;

: all-unique-permutations ( seq -- seq' )
    0 over length [ unique-permutations, ] { } make ;

! Show that it is much more efficient than all-permutations members
USE: math.combinatorics

{ 1 1 1 1 1 1 1 1 2 } [ all-permutations members drop ] time
Running time: 0.367224326 seconds

{ 1 1 1 1 1 1 1 1 2 } [ all-unique-permutations drop ] time
Running time: 5.6475e-05 seconds