【小ネタ】JSで要素の組み合わせを列挙する


下記のような、キーの数や要素数が可変のデータの組み合わせを、列挙するjavascriptコードです。
pythonにはitertoolなどの順列・組み合わせ計算を行う定番ライブラリがあるようです。

やっている事ですが、イメージとしては組み合わせを数列に置き換えています。
1桁目が2進数、3桁目が3進数、3桁目が4進数の不規則な進法で表現されていると捉えて、
n[1..234=24]までループでひたすら列挙します。

var data = {
  "1.ドリンク": ["チャイ", "ラッシー"],
  "2.副菜": ["サモサ", "ティッカマサラ", "サブジ"],
  "3.主菜": ["バターチキン", "キーマ", "ダール", "マトン"]
}

// 実行毎に結果の出力順序が一意になるようにソート
var keys = Object.keys(data).sort();

// 組み合わせの総数を事前に計算
var total = 1;
for (var key in data) {
  total *= data[key].length;
}

var q, // 商, ループ中の配列で表現できない数
    r, // 余り, ループ中の配列で表現する数
    result = []; // 組み合わせを格納する配列

// 組み合わせの総数回ループして、n番目にどの組み合わせが来るかどうかを求める
for (var n=0; n < total; n++) {
  result[n] = {};
  q = n;

  // dataのキー毎にループして、どの要素を使うか決定
  for (i=0; i<keys.length; i++) {
    key = keys[i];

    // ループ対象の配列の要素数で割った余り = その配列で表現できる数
    r = q % data[key].length;

    // ループ対象の配列の要素数で割った商 = その配列で表現できない数
    q = Math.floor(q / data[key].length);

    result[n][key] = data[key][r];
  }
}

// 出力
for (var i=0; i < result.length; i++) {
   console.log(JSON.stringify(result[i]));
}

/*
0:{"1.ドリンク":"チャイ","2.副菜":"サモサ","3.主菜":"バターチキン"}
1:{"1.ドリンク":"ラッシー","2.副菜":"サモサ","3.主菜":"バターチキン"}
2:{"1.ドリンク":"チャイ","2.副菜":"ティッカマサラ","3.主菜":"バターチキン"}
3:{"1.ドリンク":"ラッシー","2.副菜":"ティッカマサラ","3.主菜":"バターチキン"}
4:{"1.ドリンク":"チャイ","2.副菜":"サブジ","3.主菜":"バターチキン"}
5:{"1.ドリンク":"ラッシー","2.副菜":"サブジ","3.主菜":"バターチキン"}
6:{"1.ドリンク":"チャイ","2.副菜":"サモサ","3.主菜":"キーマ"}
7:{"1.ドリンク":"ラッシー","2.副菜":"サモサ","3.主菜":"キーマ"}
8:{"1.ドリンク":"チャイ","2.副菜":"ティッカマサラ","3.主菜":"キーマ"}
9:{"1.ドリンク":"ラッシー","2.副菜":"ティッカマサラ","3.主菜":"キーマ"}
10:{"1.ドリンク":"チャイ","2.副菜":"サブジ","3.主菜":"キーマ"}
11:{"1.ドリンク":"ラッシー","2.副菜":"サブジ","3.主菜":"キーマ"}
12:{"1.ドリンク":"チャイ","2.副菜":"サモサ","3.主菜":"ダール"}
13:{"1.ドリンク":"ラッシー","2.副菜":"サモサ","3.主菜":"ダール"}
14:{"1.ドリンク":"チャイ","2.副菜":"ティッカマサラ","3.主菜":"ダール"}
15:{"1.ドリンク":"ラッシー","2.副菜":"ティッカマサラ","3.主菜":"ダール"}
16:{"1.ドリンク":"チャイ","2.副菜":"サブジ","3.主菜":"ダール"}
17:{"1.ドリンク":"ラッシー","2.副菜":"サブジ","3.主菜":"ダール"}
18:{"1.ドリンク":"チャイ","2.副菜":"サモサ","3.主菜":"マトン"}
19:{"1.ドリンク":"ラッシー","2.副菜":"サモサ","3.主菜":"マトン"}
20:{"1.ドリンク":"チャイ","2.副菜":"ティッカマサラ","3.主菜":"マトン"}
21:{"1.ドリンク":"ラッシー","2.副菜":"ティッカマサラ","3.主菜":"マトン"}
22:{"1.ドリンク":"チャイ","2.副菜":"サブジ","3.主菜":"マトン"}
23:{"1.ドリンク":"ラッシー","2.副菜":"サブジ","3.主菜":"マトン"}
*/

例のデータで言えば2 * 3 * 4通りの組み合わせを求めているので、
例えば15番目の組み合わせをを求める場合、「ドリンク」で表現できる要素の数=2で割ると
商が7、余りが1、…となり、
商の7 = 「副菜」以降で表現しなければならない数
余りの1 = 「ドリンク」で表現する数

よって「ドリンク」は配列の添字[1]の要素「ラッシー」を使うと決定できます。

同様にして、商の7を「副菜」で表現できる3で割ると
商が2、余りが1、…となり、
「副菜」は配列の添字[1]の要素「ティッカマサラ」を使います。

最後の主菜では、2 / 4
商は勿論0、余りは[2]となり、
「主菜の」は配列の添字2の要素の「ダール」に決定します。


DACエンジニア採用情報

  関連記事

スクリーンショット 2015-07-31 16.41.25
【未経験からのRuby on Rails – 第3回】変数と定数

こんにちは。新卒1年目のmatsuariです。 今回はRubyに限らずプログラミングを学ぶ上で非常に重要となる「変数と定数」について、ご紹介していきます。 変数とは・・・ オブジェクトを一時的に格納しておく箱で、オブジェクトを識別するために利用します。 言葉だけでは理解が難しいかと思いますので、まず …

androidsdk10
SDKってどうやって作ってるの?【Android編】

こんにちは。4度目の投稿です。 現在私はAndroidのSDKを開発しています。 javaにもAndroidにもSDKにも手を出したのは初めてなので、最初はそもそもSDKのイメージが湧かず、ふわふわした状態で始めました。 SDKと調べても「あるソフトウェアを開発するために必要なプログラムや文書などを …

index
Android 非同期処理についてまとめてみた

Androidには、UIに影響を与えないよういくつか非同期処理が用意されています。 今回は非同期処理の代表的な ・Service ・IntentService ・HandlerThread について違いを踏まえながらまとめます! 非同期処理について(http://codezine.jp/articl …

promise
ECMAScript6を使ってみた ~「Promise」編

ECMAScript6とは 一応ちょっとだけ説明しておくと、 ECMAScript(エクマスクリプト)は、Ecma Internationalによって標準化されたスクリプト言語で、バージョン6が2015 年 6 月 17 日に標準仕様として発行されました。(以下、ES6と呼びます) ES6ではcon …

no image
Polymer on Rails

Web Componentsをご存知だろうか。これが普及すればWebの開発は画期的に変わるだろう。 説明すると長くなるので、LIGさんのにその辺はお任せして。(この記事読んでください。) 簡単に言えば、下記にあるような新たに提案されたブラウザ向けAPIの総称。 Custom Elements, 説明 …

ruby
Railsたった14行でアドサーバーAPIができた話

こんにちは。駆け出しエンジニアの近江です。 最近Railsにハマっているので、私が2年間担当しているアドサーバの、簡易版をRailsで作ってみました。 広告やキャンペーンを登録する管理画面はある前提で、ここからたった14行追加するだけでアドサーバーのHTTP APIを作りたいと思います。ついでに配信 …

chain
PyStanによるはじめてのマルコフ連鎖モンテカルロ法

はじめに こんにちは。システム開発部の中村です。 社内で行っている『データ解析のための統計モデリング入門』(所謂緑本)の輪読会に参加した所、 大変わかりやすい本だったものの、Macユーザには悲しい事に実装サンプルがWinBUGSだったため、 9章の一般化線形モデルのベイズ推定によるアプローチをPyt …

3_001
プログラミング初心者がswiftでゲームアプリ的なものを作ってみた。

こんにちは、DAC2年目のkumataです。 普段は素敵な先輩方に囲まれてインフラ周りのお仕事をさせて頂いていますが、 今回は業務とは全く関係ないプログラミングをやってみました。 全く初心者なのですが、swift+Xcodeで簡単にスマホゲーム的なものが作れました。 初心者の目線から作成方法をつらつ …

スクリーンショット 2015-07-31 16.38.02
【未経験からのRuby on Rails – 第2回】Rubyのプログラムを書いてみる(Mac)

こんにちは。新卒1年目のmatsuariです。 前回はRubyとは何か、簡単にご紹介をしましたが、 今回は実際にRubyファイルを作成して、プログラムを書いてみるところまでご紹介していけたらと思います。 Mac環境のプログラミング初心者向けです。 はじめに、Rubyのプログラムを書くためのファイルを …

rails
初心者がRailsで開発 – deviseでユーザー認証設定 -

こんにちは、2年目のYukaです。 開発部所属でありながら実は、、 実際に自分で手を動かして開発する機会がなかなかありませんでした。。 しかしついに、、、 開発初心者がRailsでWebアプリの開発に挑戦します!! 今回のゴールは社内でも使用しているGoogleアカウントで簡単にログインができるよう …