Haru32768
@Haru32768

Are you sure you want to delete the question?

If your question is resolved, you may close it.

Leaving a resolved question undeleted may help others!

We hope you find it useful!

重複順列を拡張した順列の配列をつくる

求める配列

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]];

つまりarray2array1の重複順列を拡張したみたいな順列パターンの配列です。
具体的に言うと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か月の人が作ったコードなのでだいぶ可読性低いと思いますが、処理を速くできる部分とか、そもそも再帰関数だから遅いとかあれば教えてください。

0

2Answer

Comments

  1. @Haru32768

    Questioner

    ありがとうございます。確かに計算してみたらほぼ上限でした。これは無理ですね。
    妥協してarray1を分割しようと思います。

メモリ上限を突破してしまう問題について、
配列全体を保持する必要がないといえるなら、
組み合わせを生成できるようにするという手もあるかもしれません。

const init = stem => {
  const dim = stem.map(arr => arr.length ? arr.length : -1).reverse();
  const count = dim.reduce((prev, value) => prev * Math.abs(value), 1);
  const pick = ind => {
    const d = [];
    dim.reduce((prev, value) => {
      const v = Math.abs(value);
      const r = prev % v;
      d.push(value > 0 ? r : null);
      return (prev - r) / v;
    }, ind);
    return d.reverse().map((value, index) => value !== null ? stem[index][value] : null);
  }
  return [pick, count];
}

const [arrFunc, count] = init(array1);
for (let i = 0; i < count; i++) {
  // arrFunc(i)でarray2の要素を1つずつ参照するような感じ
}
1Like

Comments

  1. @Haru32768

    Questioner

    回答ありがとうございます。
    arrFunc(i)iに見込みをつければ総当たりは免れそうですね。

Your answer might help someone💌