データ構造とアルゴリズムの配列のシリーズ---配列のデカルト積を求めます

2827 ワード
面接試験 アルゴリズム
テーマはn個の配列があって、各配列の中の要素の個数は異なって、このn個の配列のすべての並べ替えの組み合わせを求めます.例えば、A(a 1,a 2,a 3)、B(b 1,b 2)、C(c 1,c 2)の3つの配列がある.デカルト積はa 1 b 1 c 1,a 1 b 1 c 2,a 1 b 2 c 1,...である.
構想は1つの配列count[n]を設定し、n個の配列に対応し、count[i]はi番目の配列の第count]i]個の要素を表す.初期化countはいずれも0であり、各配列を遍歴し、i番目の配列については、その配列からcount[i]番目の要素を取り出す.遍歴するたびに追加される要素は極めて1つの配列です.
アルゴリズム実装

    private static LinkedList  combineArray(List nArray){
        int n=nArray.size();

        int[] count=new int[n];
        for(int i=0;icount[i]=0;
        }

        LinkedList result=new LinkedList();

        int flag=0;
        do{
            LinkedList list=new LinkedList();
            for(int i=0;icount[i]]);
            }
            result.add(list);

            //change the count array;
            flag=ChangeArrayCount(count,nArray);

        }while(flag!=1);

        return result;
    }


    private static int ChangeArrayCount(int[] count, List nArray) {
        for(int i=nArray.size()-1;i>=0;i--){
            if(count[i]==nArray.get(i).length-1){
                count[i]=0;
            }else{
                count[i]++;
                return 0;
            }
        }
        return 1;
    }
【備忘録】Ubuntu 18.04 にEmacsをインストール。設定まで
golangのflycheck