今週のアルゴリズム：最短経路の計算！(Boo/C#/Nemerle/VBでnext_permutation)

Permutation Iterator	next_permutation	URL
C#/Go/Python/Ruby/VB		まとめ含む http://qiita.com/cielavenir/items/ac96da5e3040c2edb78c
	Boo/C#/Nemerle/VB	http://qiita.com/cielavenir/items/0e07a024049017f7dea2
	Java/Groovy/Scala/Fortran/Pascal	http://qiita.com/cielavenir/items/4347fd0c6c69fa60804a
	D/Go/JavaScript/Lua/R	http://qiita.com/cielavenir/items/9e821d04f574a6623d03
Perl	HSP/PHP/Python/Ruby	http://qiita.com/cielavenir/items/006a878292c5be209231
Go2/Crystal/Kotlin/Nim/Julia		http://qiita.com/cielavenir/items/74f8d547437154c14e72
	V/Rust	http://qiita.com/cielavenir/items/cec1812999547909a9e4
D/Nemerle/JavaScript/Perl6/PHP	C/C++/Crystal/Go2/Julia Kotlin/Nim/Perl/Perl6	(github参照)

Boo

#!/usr/bin/booi
import System
import System.Array

def next_permutation[of T(IComparable)](a as (T),n as int) as bool:
    if n<0 or len(a)<n: return false
    Reverse(a,n,len(a)-n)
    i=len(a)-2
    while i>=0:
        if a[i].CompareTo(a[i+1])<0: break
        i-=1
    if i<0:
        Reverse(a)
        return false
    k=i
    i=len(a)-1
    while i>=0:
        if a[k].CompareTo(a[i]): break
        i-=1
    l=i
    z=a[k];a[k]=a[l];a[l]=z
    Reverse(a,k+1,len(a)-(k+1))
    return true

N=6
e0 as (int)=array(int,N*2)
f0 as (int)=array(int,N*2)
for i in range(N): e0[N+i]=f0[N+i]=1
Sort(e0)
Sort(f0)

r=0
i=0
e as (int)=array(int,N*2+1)
f as (int)=array(int,N*2+1)
while true:
    for i in range(N*2): e[i+1]=e[i]+e0[i]
    #数学の座標系のように左下をA、右上をBとすると、eの各インデックスiにおいて、x座標がi-e[i]、y座標がe[i]となる。
    while true:
        x=1
        for i in range(N*2):
            f[i+1]=f[i]+f0[i]
            if e[i]==f[i] and e[i+1]==f[i+1]: x=0;break
        r+=x
        #i番目の座標とi+1番目の座標が等しければ、「道に重複がある」とみなせる。
        if not next_permutation[of int](f0,len(f0)): break
    if not next_permutation[of int](e0,len(e0)): break
print(r) # 100360

C#

using System;
using System.Collections.Generic;
class CodeIQRoute{
    static bool next_permutation<T>(List<T> a,int? _n=null) where T : IComparable<T>{
        int n=_n ?? a.Count;
        if(n<0||a.Count<n)return false;
        int i;
        a.Reverse(n,a.Count-n);
        for(i=a.Count-2;i>=0;i--)if(a[i].CompareTo(a[i+1])<0)break;
        if(i<0){
            a.Reverse(0,a.Count);
            return false;
        }
        int k=i;
        for(i=a.Count-1;i>=k+1;i--)if(a[k].CompareTo(a[i])<0)break;
        int l=i;
        T z=a[k];a[k]=a[l];a[l]=z;
        a.Reverse(k+1,a.Count-(k+1));
        return true;
    }

    const int N=6;
    public static void Main(){
        int r=0,i;
        List<int>e0=new List<int>(),f0=new List<int>();
        for(i=0;i<N;i++){e0.Add(0);f0.Add(0);}
        for(i=0;i<N;i++){e0.Add(1);f0.Add(1);}
        int[] e=new int[N*2+1];
        int[] f=new int[N*2+1];
        do{
            for(i=0;i<N*2;i++)e[i+1]=e[i]+e0[i];
            do{
                for(i=0;i<N*2;i++){
                    f[i+1]=f[i]+f0[i];
                    if(e[i]==f[i]&&e[i+1]==f[i+1])break;
                }
                if(i==N*2)r++;
            }while(next_permutation(f0));
        }while(next_permutation(e0));
        Console.WriteLine(r);
    }
}

Nemerle

using System;
using System.Array;
using Nemerle.Imperative;

public class CodeIQRoute{
    static next_permutation[T](a:array[T],n:int):bool where T : IComparable[T]{
        when(n<0||a.Length<n)return false;
        mutable i:int=0;
        Reverse(a,n,a.Length-n);
        for(i=a.Length-2;i>=0;i--)when(a[i].CompareTo(a[i+1])<0)break;
        when(i<0){
            Reverse(a,0,a.Length);
            return false;
        }
        def k:int=i;
        for(i=a.Length-1;i>=k+1;i--)when(a[k].CompareTo(a[i])<0)break;
        def l:int=i;
        def z=a[k];a[k]=a[l];a[l]=z;
        Reverse(a,k+1,a.Length-(k+1));
        return true;
    }

    public static Main(): void{
        def N=6;
        mutable r:int=0;
        mutable i:int;
        def e0=array(N*2);
        def f0=array(N*2);
        for(i=0;i<N;i++){
            e0[i]=0;f0[i]=0;
            e0[N+i]=1;f0[N+i]=1;
        }
        Sort(e0);
        Sort(f0);
        def e=array(N*2+1);
        def f=array(N*2+1);
        for(i=0;i<N*2+1;i++){e[i]=0;f[i]=0;}
        do{
            for(i=0;i<N*2;i++)e[i+1]=e[i]+e0[i];
            do{
                for(i=0;i<N*2;i++){
                    f[i+1]=f[i]+f0[i];
                    when(e[i]==f[i]&&e[i+1]==f[i+1])break;
                }
                when(i==N*2)r++;
            }while(next_permutation(f0,f0.Length));
        }while(next_permutation(e0,e0.Length));
        Console.WriteLine(r);
    }
}

VB.Net

imports System
imports System.Collections.Generic
module CodeIQRoute
    function next_permutation(of T as IComparable(of T))(ByRef a as List(of T),optional ByVal _n as integer?=Nothing) as boolean
        dim n as integer=if(_n.HasValue,_n,a.Count)
        if n<0 orelse a.Count<n
            return false
        end if
        dim i as integer
        a.Reverse(n,a.Count-n)
        for i=a.Count-2 to 0 step -1
            if a(i).CompareTo(a(i+1))<0
                exit for
            end if
        next
        if i<0
            a.Reverse(0,a.Count)
            return false
        end if
        dim k as integer=i
        for i=a.Count-1 to k+1 step -1
            if a(k).CompareTo(a(i))<0
                exit for
            end if
        next
        dim l as integer=i
        dim z as T=a(k):a(k)=a(l):a(l)=z
        a.Reverse(k+1,a.Count-(k+1))
        return true
    end function

    const N=6
    sub Main(ByVal args() as String)
        dim r,i as integer
        dim e0 as List(of integer)=new List(of integer)()
        dim f0 as List(of integer)=new List(of integer)()
        for i=0 to N-1
            e0.Add(0)
            f0.Add(0)
        next
        for i=0 to N-1
            e0.Add(1)
            f0.Add(1)
        next
        e0.Sort()
        f0.Sort()
        dim e as integer()=new integer(N*2){}
        dim f as integer()=new integer(N*2){}
        do
            for i=0 to N*2-1
                e(i+1)=e(i)+e0(i)
            next
            do
                for i=0 to N*2-1
                    f(i+1)=f(i)+f0(i)
                    if e(i)=f(i) andalso e(i+1)=f(i+1)
                        exit for
                    end if
                next
                if i=N*2
                    r+=1
                end if
            loop while next_permutation(f0)
        loop while next_permutation(e0)
        Console.WriteLine(r)
    end sub
end module