Listing All Permutations (順列の全列挙)

Listing All Permutations (順列全列挙)
ported next_permutation() in C++(STL)

by nitoyon 13 Mar 2010

Embed

/**
 * Copyright nitoyon ( http://wonderfl.net/user/nitoyon )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/qSYl
 */

// Listing All Permutations (順列全列挙)
// ported next_permutation() in C++(STL)
package{
import flash.display.Sprite;
import flash.text.TextField;

public class Test extends Sprite{
    public function Test() {
        var t:TextField = TextField(addChild(new TextField()));
        t.autoSize = "left";

        var s:String = "";
        var arr:Array = [1, 2, 3, 4];
        do {
            s += arr.join(", ") + "\n";
        } while (next_permutation(arr));
        t.text = s;
    }

    private function next_permutation(arr:Array):Boolean {
        var len:int = arr.length;

        // fails if length is 0 or 1
        if (len <= 1) return false;

        // search backward
        for (var i:int = len - 2; i >= 0; i--) {
            // find a index which satisfies arr[i] < arr[i + 1]
            if (arr[i] < arr[i + 1]) {
                // search backward again...
                // find a index which satisfies arr[i] < arr[j]
                for (var j:int = len - 1; j > i; j--) {
                    if (arr[i] < arr[j]) break;
                }

                // swap arr[i] and arr[j]
                var tmp:Object = arr[j];
                arr[j] = arr[i];
                arr[i] = tmp;

                // reverse arr[i+1],arr[i+2],...,arr[len-1]
                for (j = 1; ; j++) {
                    if (i + j >= len - j) break;
                    tmp = arr[i + j];
                    arr[i + j] = arr[len - j];
                    arr[len - j] = tmp;
                }

                // found
                return true;
            }
        }

        // not found
        return false;
    }
}
}