#/***********************************************************
#    permsign.rb -- 弥垂の射规
#***********************************************************/
N = 4

def sign( v )
    w = []

    for i in 1..N; w[v[i]] = i; end
    p = 1
    for i in 1...N
        j = v[i]
        if (j != i) 
            v[w[i]] = j;  w[j] = w[i];  p = -p
        end
    end
    return p
end

def nextperm( a )
    i = N - 1
    a[0] = 0;  # 戎客 
    while (a[i] >= a[i + 1]); i -= 1; end
    if (i == 0); return 0; end  # 窗位 
    j = N
    while (a[i] >= a[j]); j -= 1; end
    t = a[i];  a[i] = a[j];  a[j] = t
    i += 1;  j = N
    while (i < j) 
        t = a[i];  a[i] = a[j];  a[j] = t;  i += 1;  j -= 1
    end
    return 1;  # 踏位 
end

def test1
    a = []
    v = []

    printf("辑今及界进:\n")
    count = 0
    for i in 1..N; a[i] = i; end
    begin 
        printf("%5d: ", count += 1)
        for i in 1..N; printf("%4d", v[i] = a[i]); end
        printf("  %s弥垂\n", (sign(v) == 1) ? "饿" : "瘩")
    end while (nextperm(a) == 1)
end

def test2
    p = []
    c = []
    v = []

    printf("高垂による界误栏喇:\n")
    count = 0
    for i in 1..N; c[i] = p[i] = i; end
    c[N + 1] = 0;  # 戎客 
    k = 2; while (k <= N) 
        if (k & 1); i = 1; else; i = c[k]; end
        t = p[k];  p[k] = p[i];  p[i] = t
        printf("%5d: ", count += 1)
        for i in 1..N; printf("%4d", v[i] = p[i]); end
        printf("  %s弥垂\n", (sign(v) == 1) ? "饿" : "瘩")
        k = 2; while (c[k] == 1); c[k] = k; k += 1; end
        c[k] -= 1
    end
end

test1
test2

exit 0