Listing All Permutations (順列の全列挙)

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

forked:0
favorite:5
lines:38
license : MIT License
modified : 2010-03-14 00:57:35

Embed: Tweet

// 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;
    }
}
}

Code Fullscreen

Preview Fullscreen