JavaScript アルゴリズム

Question

0からnまでを要素として含む同じ3つの配列から、
重複のないように、3つずつ要素を含む配列を作成する関数はどう定義すればいいでしょうか？

function make3Array (n){
　let arr = [];
  // 処理
  // return arr;
}

のような関数を考えています。

例えば、nが9の場合は、

[0,1,2,3,4,5,6,7,8,9]
[0,1,2,3,4,5,6,7,8,9]
[0,1,2,3,4,5,6,7,8,9]

を重複のないように並べ替えて、以下のような2次元配列を生成したいです。

[
　[0,3,7],
　[2,0,8],
　[5,6,2],
　[7,2,6],
　[1,8,3],
　[8,7,1],
　[9,1,5],
　[6,9,4],
　[3,4,9],
　[4,5,0],
]

ご教授いただけるとありがたいです。
よろしくお願いします。

Comments

[hatena19]

内側の３の数字も重複がないようにということですか。
例えば [2,2,3] はNG。

[jun68ykt]

こんにちは。ご質問の事例だと、並べ替え後の2次元配列には 0 から 9 までの数字が、各々 3個ずつ存在しているという理解でよいでしょうか？（ちなみにご質問に挙げられている、並べ替え後の2次元配列には、0 が 2個しか含まれていなく、5 が ４個含まれています。）

[t-cool]

質問での例が間違えていました。
nが9の場合は、0 から 9 までの数字が、各々 3個ずつ存在しているという意味でした。
あと、並び順はランダムで並べたいです。説明不足ですいません。

[t-cool]

"内側の３の数字も重複がないようにということですか。例えば [2,2,3] はNG。"

はい。内側の数字も重複がなく、ランダムな並びに並べ替えたいです。

Answer 1

[
　[0,1,2],
　[1,2,3],
　[2,3,4],
　[3,4,5],
　[4,5,6],
　[5,6,7],
　[6,7,8],
　[7,8,9],
　[8,9,0],
　[9,0,1],
]

こう並べるのが簡単です。必要なパラメーターは n だけで、元の配列のことは考える必要ありません。

[8,9,0]

これは次のように求められます。

[(8+0)%(n+1),(8+1)%(n+1),(8+2)%(n+1)]

追記

const n = 9;
const rows = n + 1;
const columns = 3;

let exclude = [...Array(columns).keys()].map(column => []);

const dest = [...Array(rows).keys()].map(row => {
	let result = [];
	for (let i = 0; i < columns; i++) {
		let array = [...Array(rows).keys()].
			filter(a => exclude[i].findIndex(b => a === b) < 0).
			filter(a => result.findIndex(b => a === b) < 0);
		const r = Math.floor(Math.random() * array.length);
		result.push(array[r]);
		exclude[i].push(array[r]);
	}
	return result;
});

console.log(dest);

Comments

[t-cool]

ご助言ありがとうございます。
質問の例のように、並び順はランダムで並べたいです。
質問の説明が中途半端ですいません。

[tanishi_a]

組み合わせの配列を作ったあと、
その配列をシャッフルするのと分けたら良いと思いますよ。

Answer 2

冗長だし、がっさいですが、
（しかも書き方も古い）
下記でいかがでしょうか。

発想を変え、三つの配列を、
いったん一つの配列にまとめ、
そこから、一個一個にランダムにとってきた数値を入れていくやり方です。

正直、同じ発想でも、もっとスマートな方法があるかと。
（while使いまくってるのもけっこう危険）

function make3Array (n, column) {
　const arr = [],
    baseArr = [];

  // ベースとなる、n * columnの配列を作成
  for (let ci = 0; ci < column; ci++) {
    const insertOneArr = [];
    for (let ni = 0; ni < n + 1; ni++) {
       insertOneArr.push(ni);
    }
    baseArr.push(insertOneArr);
  }

  // ベースを一つにまとめた配列を用意
  const allSerial = [];
  baseArr.forEach(val => {
    val.forEach(vi => {
      allSerial.push(vi);
    });
  });

  // まとめた配列がなくなるまで繰り返す
  while (allSerial.length > 0) {
    let insertArr = [];
    // columnの数だけ、入るよう繰り返す
    while (insertArr.length <= column && allSerial.length > 0) {
      // まとめた配列のランダムのインデックスを用意
      let rn = Math.floor( Math.random() * allSerial.length );
      // 一つの配列にその数値が含まれる限り、ランダムインデックスを入れなおす
      while ( insertArr.includes(allSerial[rn]) ) {
        rn = Math.floor( Math.random() * allSerial.length );
      }
      // 値渡しにするために、変数に格納
      const ti = allSerial[rn];
      // 一つの配列に格納
      insertArr.push(ti);
      // まとめ配列の数値要素を削除
      allSerial.splice(rn, 1);
      // 一つの配列が、columnの数になったら、最終的に返したい配列にプッシュ
      if (insertArr.length == column) {
        // 値渡しにするため、concatメソッドを使用
        arr.push(insertArr.concat());
        // まとめ配列が残っている限り、一つ要素用配列をクリア
        if (allSerial.length > 0) {
          insertArr = [];
        }
      }
    }
  }

  return arr;
}

console.log(make3Array(9, 3));

Answer 3

こんにちは

ご質問にある

0からnまでを要素として含む同じ3つの配列から、

という趣旨に沿って、これら3つの配列 ar1 , ar2, ar3 を作成するステップを以下のように考えました。

(1) 与えられた n によって、 0 から n までを要素とする配列 ar1 を作成する。

例えば、 n が 9 のとき、 ar1は、 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

(2) 上記 (1) で得られた ar1 をランダムに並び替え、かつ、以下の条件

• 0 以上 n 以下の任意の整数 i に対して、ar1[i] ≠ ar2[i]

を満たす配列 ar2 を作成する。

例えば、 n が 9 のとき、 ar2として、 [6, 8, 4, 9, 5, 1, 7, 3, 0, 2]　を作成

(3) 上記 (1) で得られた ar1 をランダムに並び替え、かつ、以下の条件

• 0 以上 n 以下の任意の整数 i に対して、ar1[i] ≠ ar3[i] かつ ar2[i] ≠ ar3[i]

を満たす配列 ar3 を作成する。

例えば、 n が 9 のとき、 ar2として、 [2, 6, 5, 4, 0, 8, 1, 9, 7, 3]　を作成

(4) 上記 (1)(2)(3) で得られた ar1 , ar2 , ar3 の同じ位置の要素を集めた配列を要素とした配列を作成

上記の例だと、以下が得られます。

[[0, 6, 2], [1, 8, 6], [2, 4, 5], [3, 9, 4], [4, 5, 0], [5, 1, 8], [6, 7, 1], [7, 3, 9], [8, 0, 7], [9, 2, 3]]

以下は上記の各ステップをコードにしたものです。

function sample(ary) {  
  return ary[Math.floor(Math.random() * ary.length)];     
}

function make3Array (n) {

  // 0 から n までを要素として含む配列 ar1 を作成
  const ar1 = [...Array(n+1)].map((_, i) => i)
  
  // ar1 と同じ位置に同じ要素を持たない配列 ar2 を作成
  let ar2
  while(true) {
    ar2 = []
    ar1.forEach((_, i) => {
      const candidates = ar1.filter(e => e !== ar1[i] && !ar2.includes(e))
      ar2.push(sample(candidates))
    })
    if (typeof ar2[n] !== 'undefined')
      break    
  }
  
  // ar1, ar2 と同じ位置に同じ要素を持たない配列 ar3 を作成
  let ar3
  while(true) {
    ar3 = []
    ar1.forEach((_, i) => {
      const candidates = ar1.filter(e => e !== ar1[i] && e !== ar2[i] && !ar3.includes(e))
      ar3.push(sample(candidates))
    })
    if (typeof ar3[n] !== 'undefined')
      break 
  }
  
  // ar1, ar2, ar3 の同じ位置の要素を集めた配列を要素とした配列に変換
  return ar1.map((_, i) => [ar1[i], ar2[i], ar3[i]])  
}

• **動作確認用CodePen: ** https://codepen.io/jun68ykt/pen/oNvKQKd?editors=0012

以上、参考になれば幸いです。

追記

以下、別解です。

3つの配列

を、 ar1, ar2, ar3 として作ることは先の回答と変わりありませんが、配列をシャッフルするために lodash の _.shuffle を使い、配列を回転（rotate)させる関数を、stackoverflow のこの回答から拝借します。

function arrayRotate(arr, reverse) {
  if (reverse) arr.unshift(arr.pop());
  else arr.push(arr.shift());
  return arr;
}

function make3Array (n) {

  // 0 から n までをランダムな順番で含む配列を作成する。
  const ar1 = _.shuffle([...Array(n+1)].map((_, i) => i))
  
  // ar1 をローテートした配列を得る
　const ar2 = arrayRotate([...ar1])
 
  // ar2 をローテートした配列を得る 
　const ar3 = arrayRotate([...ar2])
  
  // ar1, ar2, ar3 の同じ位置の要素を集めた配列を要素とした配列を得る
  const ar = ar1.map((_, i) => [ar1[i], ar2[i], ar3[i]])

  // 上記で得られた配列をシャッフルした配列を返す
  return _.shuffle(ar)
}

• **動作確認用CodePen: ** https://codepen.io/jun68ykt/pen/pozMLXy?editors=0012

Comments

[退会済みユーザー]

この方法だと乱数の出目によってはar3が正しく生成できないことはありませんか?たとえば、n=4でar1=[0, 1, 2, 3, 4], ar2=[2, 4, 0, 1, 3], ar3=[4, 2, 1, 0, undefined] みたいな感じで。n=9であれば発生頻度は低くなるとは思いますが確率0にはできないのでは。

[jun68ykt]

@kichirb3さん
ご指摘ありがとうございます。確認したところ、おっしゃる通りでした。

@t-coolさん
上記の回答で、先に書いたほうのコードだと、kichirb3さんからご指摘のように常に正しく動作するとはいえないものになっております。こちらのほう、修正できたら修正します。追記のほうに記載した別解のほうもご検討ください。

[Zuishin]

別解はちょっとずるいですね。数字が斜めに並んで規則性がはっきり出ています。

[jun68ykt]

@Zuishinさん
ご指摘ありがとうございます。最後にもう一度シャッフルして数字が斜めに並ばないようにしました。

[Zuishin]

やっぱりよく見ると規則性が見て取れますが、ぱっと見わかりません。こんな方法もあるんですね。

[jun68ykt]

@Zuishinさん
もうひとこえやろうと思えば、ar1からar2を得るとき、および、 ar2 からar3 を得るときの、ローテートの回数が現状1つずつなのを、このローテート回数も乱数で得るようにすればよいかなと思います。（回数によっては、a1, ar2, ar3 のいずれか２つが一致してしまうこともあるので、それを避けるような回数を得る必要はありますが。）

[jun68ykt]

@kichirb3さん
@t-coolさん

kichirb3さんの先のコメントからのご指摘の件に対応した修正版を、回答のほうに反映しました。修正の方法としては単純で、ar2 および ar3 を作る際に、undefined を含まないように作ることができるまで、作成を繰り返し試みます。

Answer 4

配列をシャッフルするアルゴリズムはフィッシャー–イェーツのシャッフル - Wikipediaが有名ですね。
JSでの実装例は下記。
JavaScript アルゴリズムで配列をシャッフルする - Qiita

一つ目の[0,1,2,3,4,5,6,7,8,9]の配列を上記の方法でシャッフルする。

二つ目の[0,1,2,3,4,5,6,7,8,9]の配列をシャッフルして、一つ目と比較して重複があったら再トライ、重複がないのが出現するまで繰り返す。

三つ目の配列もシャッフルして、一つ目、二つ目と比較して重複がなくなるまで繰り返す。

というアルゴリズムはどうでしょう。

無駄が多いのでもっとスマートなアルゴリズムかあるとは思います。