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


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

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

[code lang=”js”]
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.主菜":"マトン"}
*/
[/code]

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

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

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

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


DACエンジニア採用情報

  関連記事

no image
Polymer core-ajax の使い方

Polymerのcore-ajaxの使い方。 まずは、index.html [code language=”html” title=”index.html”] <!doctype html> <html> <head&gt …

Bootstrapのモーダル機能で多重表示する際に解決しなければならない2つの問題

はじめに みなさんこんにちは、プロダクト開発本部の亀梨です。 普段はXmediaOneというメディアプランニング・広告運用管理・トラッキング・マーケティング分析を行う 統合プラットフォームの開発・保守を担当しています。 エンジニアの皆さん、デザインってどうしてます? わたくしはプライベートでとあるW …

Qiita Team API と Google Spread Sheet でチーム日報を生成する

チーム日報を活用する MarketOne 開発チームでは複数拠点に分かれての開発を行っています。リモート開発が中心となると口頭でのコミュニケーションに限界があるため、テキストベースのコミュニケーションの比重が高い状態にあります。 チケットシステムやソースコード管理ツール上の議論はもちろんおこなってい …

iOS端末情報をTreasureDataに送るアプリをswiftで作ってみた。

はじめまして、2年目のOyamanです。 通常業務とは別のことになりますが、Swiftに触れる機会が少しあったので、スマホ関連の記事を書かせていただきます。 はじめに SwiftとTreasureDataのSDKを使って、 iOSの端末情報をTreasureDataへ送るアプリを作ってみます。 今回 …

no image
【未経験からのRuby on Rails – 第1回】楽しく書けるプログラミング言語 “Ruby” とは

こんにちは、はじめまして。新卒1年目のmatsuari(女子)です。 この度、Rubyの勉強を始めることになりまして、 まずはたくさんあるプログラミング言語の中で、なぜ自分がRubyを学ぶのか? しっかりと把握した上で学習に取り組んでいきたいと考え、『Rubyとは何か?』調べました。 超基礎的なこと …

no image
【小ネタ】Javascriptのconsoleオブジェクトをもっと便利に使う方法

すごく便利なconsoleオブジェクトですが、ブラウザによってサポートされているメソッドが なかったり、そもそもconsoleオブジェクトが使えなかったりと、たまに不便だったりします。 そんなときによく使う便利なコード。 [code language=”javascript” …

no image
Angular.jsのvalueとfactoryの違いを考える

次のようなHTMLがあったとする。 [code language=”html”] <!doctype html> <html lang="jp" ng-app="App"> <head> <me …

【未経験からのRuby on Rails – 第2回】Rubyのプログラムを書いてみる(Mac)

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

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

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

【未経験からのRuby on Rails – 第4回】Railsアプリケーション開発をしよう! 〜開発の準備編〜

こんにちは。新卒のmatsuariです。 Rubyについてまだまだ知るべきことはたくさんありますが、とにかく早くアプリを作りたい! ということで、今回はアプリ開発の準備に取り掛かっていきます。 Rubyはアプリを作成しながら、同時に学んでいきたいと思います。 Railsアプリケーション開発の準備《 …