重複順列を拡張した順列の配列をつくる
求める配列
Javascriptで次の例array1
から次のarray2
を作成したい。
(実行はGoogle Apps Script)
array1 = [[0,1,2],[],[3,4,5]];
array2 = [[0.0, null, 3.0], [0.0, null, 4.0], [0.0, null, 5.0],
[1.0, null, 3.0], [1.0, null, 4.0], [1.0, null, 5.0],
[2.0, null, 3.0], [2.0, null, 4.0], [2.0, null, 5.0]];
つまりarray2
はarray1
の重複順列を拡張したみたいな順列パターンの配列です。
具体的に言うとarray1
の二次元目の配列から一つずつ要素を抽出した配列の配列がarray2
です。
発生している問題
一応上記を満たす関数を作ってみましたが、処理が多すぎてOOMエラーをはいてしまいます。
以下がその関数
const dendrogram = stem => {
let answer =[];
let returnedArray = [];
if(stem.length===1){
let lastArray = [];
if(stem[0].length===0){
lastArray.push([null]);
}else{
for(let last of stem[0]){
lastArray.push([last]);
}
}
answer=JSON.parse(JSON.stringify(lastArray));
}else{
returnedArray = JSON.parse(JSON.stringify(dendrogram(stem.slice(1))));
if(stem[0].length===0){
let returned = JSON.parse(JSON.stringify(returnedArray));
answer = returned.map(ar=>{
ar.unshift(null);
return ar;
});
}else{
let slisedArray = [];
for(let n of stem[0]){
let returned = JSON.parse(JSON.stringify(returnedArray));
slisedArray.push(returned.map(ar=>{
ar.unshift(n);
return ar;
}));
}
for(let sliced of slisedArray){
for(let sl of sliced){
answer.push(sl);
}
}
}
}
return answer;
};
arry1
の長さが小さければ処理できますが、自分が求めているarray1
がこんな感じです。
array1 = [[0.0, 1.0, 2.0, 3.0, 4.0, 5.0], [], [], [0.0], [0.0, 1.0, 2.0,
3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0,
16.0, 17.0, 18.0, 19.0, 20.0], [], [0.0], [], [0.0, 1.0, 2.0, 3.0, 4.0,
5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0, 17.0,
18.0, 19.0, 20.0], [], [0.0, 1.0, 2.0, 3.0, 4.0, 5.0], [], [], [0.0, 1.0,
2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0,
15.0, 16.0, 17.0, 18.0, 19.0, 20.0], [], [], [0.0], [0.0], [0.0, 1.0, 2.0,
3.0, 4.0, 5.0], [0.0], [], [], [0.0], [], [], [0.0, 1.0, 2.0, 3.0, 4.0,
5.0], [], [0.0], [], [], [0.0], [], [], [0.0, 1.0, 2.0, 3.0, 4.0, 5.0],
[0.0, 1.0, 2.0, 3.0, 4.0, 5.0], [0.0, 1.0, 2.0, 3.0, 4.0, 5.0], [], []];
たったこれだけでarray2
の長さは約$26$億...
こちらの都合でarray1
の長さは$38$と決まっていますが、
二次元目の配列の長さは最大 ${}_{39} C_5 =575,757$ とふざけた数ですが、そうはならないように抑えています。
処理を速くしたい
プログラミング始めて1か月の人が作ったコードなのでだいぶ可読性低いと思いますが、処理を速くできる部分とか、そもそも再帰関数だから遅いとかあれば教えてください。