かもメモ

自分の落ちた落とし穴に何度も落ちる人のメモ帳

javascript 2つの配列からそれぞれランダムに値を取り出しかつ値が被らないようにしたい。

Teratailに JavaScriptでかぶらないように変数を分配したい(14969)|teratail というクイズみたいなのがあったので、面白そうだから考えてみました。

各配列の値が同じにならない様に取り出すパティーン。

各配列の中に同じ文字列があって、これが被らないようにしたいパティーン。

  1. 各配列の並び順のパターンを作成
  2. それぞれどの並び順にするか決める。
  3. それぞれの配列を並び順に調べて、値(文字列)が被るものがあると 2. をやり直し
  4. 並び順が決まったら前から順番に取り出す。
var argA = ["りんご", "ばなな", "きうい", "みかん"];
var argB = ["りんご", "ばなな", "きうい"];

// 配列の長さを同じにする
var adjustLength = function(arg1, arg2) {
  var l1 = arg1.length,
      l2 = arg2.length,
      gap = Math.abs(l1 - l2),
      adjustArg;
  if(gap) {
    adjustArg = (l1 > l2)? arg2:arg1;
    for(var i=0; i<gap; i+=1) {
      adjustArg[ adjustArg.length ] = "無し";
    }
  }
};

// 取り出し方の全パターンを作成して返す
var generatePatterns = function(arg) {
  var patterns = [];
  var sortArg = function(allPtns, ptnArg, post, n) {
    if(n > 0) {
      var next, rest;
      for(var i=0, l=post.length; i<l; i+=1) {
        rest = post.slice(0);
        next = rest.splice(i, 1);
        sortArg(allPtns, ptnArg.concat(next), rest, n-1);
      }
    } else {
      console.log(ptnArg);
      allPtns[ allPtns.length ] = ptnArg;
    }
  };
  sortArg(patterns, [], arg, arg.length);
  return patterns;
};

!function() {
  var i = 0,
      l = 0,
      allPatternsA,
      allPatternsB,
      randA,
      randB,
      ptnA,
      ptnB,
      isSame = true;

  adjustLength(argA, argB);
  console.log('▼ argAの取り出し方の全パターン ▼');
  allPatternsA = generatePatterns(argA);
  console.log('▼ argBの取り出し方の全パターン ▼');
  allPatternsB = generatePatterns(argB);

  randA = Math.floor( Math.random() * allPatternsA.length );
  ptnA = allPatternsA[randA];

  while(isSame) {
    randB = Math.floor( Math.random() * allPatternsB.length );
    ptnB = allPatternsB[randB];
    isSame = false;
    for(i=0, l=ptnA.length; i<l; i+=1) {
      // 取り出し順の値が被らないかチェック
      if(ptnA[i] === ptnB[i]) {
        isSame = true;
        break;
      }
    }
  }

  console.log('▼ argA, argB それぞれの取り出し順 ▼');
  console.log(ptnA, ptnB);

  console.log('▼ 決まった取り出し順に基いて順番に取り出す ▼');
  for(i=0, l=ptnA.length; i<l; i+=1) {
    var m1 = ptnA[i],
        m2 = ptnB[i];
    console.log(m1 + 'と' + m2);
  }
}();

argAのりんごとargBのりんごを同じものとして、同じ文字列が被らないだともっとコード量の少ない処理にできそうな気がします。


各配列の同じindexを取り出さないようにするパティーン

配列の文字列ではなく同じindexのものを取り出さないパティーンを考えてみました。

  1. 配列の長さから取り出し順のパターンを作成する
  2. それぞれの配列の取り出し順をランダムに選択する
  3. 取り出すindexを順番に調べて同じindexがあったら 2. をやり直し
  4. 配列長でループさせて、各取り出し順のindexの値を配列から取り出す
var Division1 = ["阿武隈", "川内", "神通", "那珂"];
var Division2 = ["暁", "響", "雷", "電"];

// 配列の長さを同じにする
var adjustLength = function(arg1, arg2) {
  var l1 = arg1.length,
      l2 = arg2.length,
      gap = Math.abs(l1 - l2),
      adjustArg;
  if(gap) {
    adjustArg = (l1 > l2)? arg2:arg1;
    for(var i=0; i<gap; i+=1) {
      adjustArg[ adjustArg.length ] = "なし!";
    }
  }
};

// 取り出し方のパターンを作成
var generatePatterns = function(n) {
  var arg = [],
      patterns = [];
  for(var i=0; i<n; i+=1) {
    arg[i] = i;
  }

  var sortArg = function(tmp, post, n) {
    if(n > 0) {
      var next, rest;
      for(var i=0, l=post.length; i<l; i+=1) {
        rest = post.slice(0);
        next = rest.splice(i, 1);
        sortArg(tmp.concat(next), rest, n-1);
      }
    } else {
      console.log(tmp);
      patterns[ patterns.length ] = tmp;
    }
  };
  console.log('▼ 取り出し順の全パターン ▼');
  sortArg([], arg, arg.length);
  return patterns;
};

!function() {
  var i = 0,
      l = 0,
      patterns,
      rand1,
      rand2,
      ptn1,  // Division1 の取り出し順
      ptn2,  // Division2 の取り出し順
      isSame = true;

  adjustLength(Division1, Division2);
  patterns = generatePatterns( Division1.length );

  rand1 = Math.floor( Math.random() * patterns.length );
  ptn1 = patterns.splice(rand1, 1)[0];

  while(isSame) {
    rand2 = Math.floor( Math.random() * patterns.length );
    ptn2 = patterns.splice(rand2, 1)[0];
    isSame = false;
    for(i=0, l=ptn1.length; i<l; i+=1) {
      // 取り出し順の値が被らないかチェック
      if(ptn1[i] === ptn2[i]) {
        isSame = true;
        break;
      }
    }
  }
  console.log('▼ Division1, Division2 それぞれの取り出し順 ▼');
  console.log(ptn1, ptn2);

  console.log('▼ 決まった取り出し順に基いて順番に取り出す ▼');
  for(i=0, l=ptn1.length; i<l; i+=1) {
    var m1 = Division1[ ptn1[i] ],
        m2 = Division2[ ptn2[i] ];
    console.log(m1 + 'と' + m2 +'のペアで訓練!');
  }
}();

 

感想

すごい冗長なものになってしまいました。。。
もっとCOOLな処理ができそうな気がします。そんな方法があったら教えてください。

あ、全然関係無いですが、自称本業で作った 第一水雷戦隊のてぬぐいが とらのあなさんで委託が始まりました。
よろしければ見てみてください。
第一水雷戦隊 軍艦巻き てぬぐい - チャイカ舎
 

追記

一方の配列の取り出し方をランダムに決定して、もう一方の配列の取り出し方を被らないように決めるのがコード量少なそう

  1. 配列Aをシャッフルするして順番を入れ替える ※ 配列Aの取り出し方はココで確定
  2. 配列Bをシャッフルする
  3. インデックス順に各配列の要素を取り出してチェック。1回でも値が同じ場合があると2をやり直し
  4. インデックス順に各配列の要素を取り出す
var arg1 = ["りんご", "ばなな", "きうい", "みかん"];
var arg2 = ["りんご", "ばなな", "きうい", "みかん"];

// fisher-yates アルゴリズム ... シャッフルするアルゴリズム
var shuffle = function(arg) {
  var i, j, l, tmp;
  for(l=arg.length, i=l-1; i>0; i-=1) {
    j = Math.floor(Math.random() * (i+1));
    tmp = arg[i];
    arg[i] = arg[j];
    arg[j] = tmp;
  }
  return arg;
};

var sameFlg = true,
    i = 0,
    len = arg1.length;
// arg1をシャッフル
arg1 = shuffle(arg1);

while(sameFlg) {
  // arg2をシャッフル
  arg2 = shuffle(arg2);
  // 順番に取り出して同じ値が出てくるか調べる
  sameFlg = false;
  for(i = 0; i<len; i+=1) {
    console.log(arg1[i], arg2[i]);
    if(arg1[i] === arg2[i]) {
      sameFlg = true;
      console.log('>>> 残念。被る並び順だった!!');
      break;
    }
  }
}

console.log('▼ arg1, arg2 それぞれの取り出し順 ▼');
console.log(arg1, arg2);
for (i = 0; i < len; i+=1) {
  console.log(arg1[i] + " と " + arg2[i]);
}

いずれにせよ

A. 配列Aの`りんご`と配列Bの`りんご`を区別する  
  = それぞれの袋の中から1つづつ取り出しす かつ 取り出されたモノ(の種類)が被らないようにする  
B. `りんご`というも区別できないモノのが2つ有るとする  
  = 大きな袋に全部入れてランダムに2つ取り出して、取り出されたモノが被らないようにする

のどちらかによって、ベストなコードは変わってくると思います。 僕が書いたのはいずれも、A. のパティーンの場合です。

後、恥ずかしながらfisher-yates アルゴリズムというのを初めて知りました。
勉強になった!  


参考

艦隊これくしょん -艦これ- 第六駆逐隊 第一種略帽

艦隊これくしょん -艦これ- 第六駆逐隊 第一種略帽