#/***********************************************************
#    genperm.rb -- 順列生成
#***********************************************************/

#**** 共通の定義 ****

N = 4
$count = 0
$p = []

def show
    $count += 1;  printf("%5d: ", $count)
    for i in 0...N; printf(" %d", $p[i]); end
    printf("\n")
end

#**** 方法 1 ****

$ok = []

def put(pos,  k)
    $p[pos] = k
    if (pos == N - 1); show()
    else 
        $ok[k] = false
        for j in 1..N
            if ($ok[j]); put(pos + 1, j); end
        end
        $ok[k] = true
    end
end

def genperm1
    $count = 0
    for k in 1..N; $ok[k] = true; end
    for k in 1..N; put(0, k); end
end

#**** 方法 2 ****

def put2(pos,  k)
    $p[pos] = k
    if (k == N); show()
    else
        for j in 0...N
            if ($p[j] == 0); put2(j, k + 1); end
        end
    end
    $p[pos] = 0
end

def genperm2
    $count = 0
    for pos in 0...N; $p[pos] = 0; end
    for pos in 0...N; put2(pos, 1); end
end

#**** 方法 3 ****

def perm(i)
    if (i > 0) 
        perm(i - 1)
        (i - 1).downto(0) do |j|
            t = $p[i];  $p[i] = $p[j];  $p[j] = t
            perm(i - 1)
            t = $p[i];  $p[i] = $p[j];  $p[j] = t
        end
    else
        show()
    end
end

def genperm3
    $count = 0
    for i in 0...N; $p[i] = i + 1; end
    perm(N - 1)
end

#**** 方法 4 ****

def genperm4
    c = []

    $count = 0
    for i in 0...N; $p[i] = i + 1; end
    for i in 1..N; c[i] = i; end         # c[N]≠0 は番人
    k = 1
    while (k < N) 
        if ((k & 1) == 1); i = c[k]; else; i = 0; end
        t = $p[k];  $p[k] = $p[i];  $p[i] = t
        show()
        k = 1
        while (c[k] == 0);  c[k] = k;  k += 1;  end
        c[k] -= 1
    end
end

#**** 各方法のテスト ****

printf("方法 1\n");  genperm1()
printf("方法 2\n");  genperm2()
printf("方法 3\n");  genperm3()
printf("方法 4\n");  genperm4()

exit 0