65 lines
1.1 KiB
Text
65 lines
1.1 KiB
Text
class SuperPermutation {
|
|
@super : static : Char[];
|
|
@pos : static : Int;
|
|
@cnt : static : Int[];
|
|
|
|
function : Main(args : String[]) ~ Nil {
|
|
max := 12;
|
|
@cnt := Int->New[max];
|
|
@super := Char->New[0];
|
|
|
|
for(n := 0; n < max; n += 1;) {
|
|
"superperm({$n}) "->Print();
|
|
SuperPerm(n);
|
|
len := @super->Size() - 1;
|
|
"len = {$len}"->PrintLine();
|
|
};
|
|
}
|
|
|
|
function : native : FactSum(n : Int) ~ Int {
|
|
s := 0; x := 0; f := 1;
|
|
while(x < n) {
|
|
f *= ++x; s += f;
|
|
};
|
|
return s;
|
|
}
|
|
|
|
function : native : R(n : Int) ~ Bool {
|
|
if(n = 0) {
|
|
return false;
|
|
};
|
|
|
|
c := @super[@pos - n];
|
|
if(--@cnt[n] = 0) {
|
|
@cnt[n] := n;
|
|
if(<>R(n - 1)) {
|
|
return false;
|
|
};
|
|
};
|
|
@super[@pos++] := c;
|
|
|
|
return true;
|
|
}
|
|
|
|
function : SuperPerm(n : Int) ~ Nil {
|
|
@pos := n;
|
|
len := FactSum(n);
|
|
|
|
tmp := Char->New[len + 1];
|
|
Runtime->Copy(tmp, 0, @super, 0, @super->Size());
|
|
@super := tmp;
|
|
|
|
for(i := 0; i <= n; i += 1;) {
|
|
@cnt[i] := i;
|
|
};
|
|
|
|
for(i := 1; i <= n; i += 1;) {
|
|
@super[i - 1] := i + '0';
|
|
};
|
|
|
|
do {
|
|
r := R(n);
|
|
}
|
|
while(r);
|
|
}
|
|
}
|