再帰を使わない順列生成 : 1から9の数字を1回ずつ使ってできる数を、小さい方から順に列挙する(アルゴリズム編)
1から9の数字を1回ずつ使ってできる数を、小さい方から順に列挙するアルゴリズムです。
次に小さい数を求めるアルゴリズム
ある数N
が与えられたとき、その数に使用されている数字を使用してできる数で、N
の次に大きい数を生成します。
① N
の10^i
の桁を、n[i]
で表します
②n[i]
を桁小さい方からみていき、初めてn[i] < n[i-1]
となるi
を求めます
③n[0]
からn[i-1]
まで順番に見ていき、n[i]
より初めて大きくなるものを求めます。求めたものをn[j]
とします。
④n[i]
とn[j]
を入れ替えます
⑤n[0]
からn[i-1]
を逆順にします
この説明だとよくわからないと思うので、具体的な数字でアルゴリズムを確かめてみましょう。
アルゴリズムを適用した例
N=179836542
とします。
① N
の10^i
の桁を、n[i]
で表します
以下のようになります。
n[0] = 2 // 一の位 (10^0) n[1] = 4 // 十の位 (10^1) n[2] = 5 // 百の位 (10^2) n[3] = 6 // 千の位 (10^3) n[4] = 3 // 万の位 (10^4) n[5] = 8 // 十万の位 (10^5) n[6] = 9 // 百万の位 (10^6) n[7] = 7 // 千万の位 (10^7) n[8] = 1 // 億の位 (10^8)
②n[i]
を桁小さい方からみていき、初めてn[i] < n[i-1]
となるi
を求めます
小さい桁から見て行ったとき、3 < 6
のとき初めて数が小さくなります。このときn[4] < n[3]
なので、i = 4
です。
③n[0]
からn[i-1]
まで順番に見ていき、n[i]
より初めて大きくなるものを求めます。求めたものをn[j]
とします。
10^4
より下の桁で3
より大きい数が初めて出てくるのは4
です。n[1] = 4
なので、j = 1
です。
④n[i]
とn[j]
を入れ替えます
3
と4
を入れ替えます。入れ替えた後も、n[0]
からn[i-1]
までは昇順に並んでいますね。
⑤n[0]
からn[i-1]
を逆順にします
入れ替えた結果です。
以上で、179836542
から、次に大きい数である、179842356
を得ることができました。
小さい方から列挙するアルゴリズム
1から9の数字を1回ずつ使ってできる数の中で、一番小さい数は123456789
です。
ここから、上記アルゴリズムを使用して、次に小さい数を求めます。
さらにそこから得られた数に対して上記アルゴリズムを適用します。
これを繰り返すことによって順列を取り出すことができます。
手順の、
②n[i]
を桁小さい方からみていき、初めてn[i] < n[i-1]
となるi
を求めます
ここで該当するi
がなくなったら終了です。
数字が重複しているとき
数が重複しているとき、も上記アルゴリズムはうまく動作します。
例えばN=652331
の場合を考えます。
① N
の10^i
の桁を、n[i]
で表します
②n[i]
を桁小さい方からみていき、初めてn[i] < n[i-1]
となるi
を求めます
こちらは上記と同じで、
n[0] = 1 // 一の位 (10^0) n[1] = 3 // 百の位 (10^2) n[2] = 3 // 千の位 (10^3) n[3] = 2 // 万の位 (10^4) n[4] = 5 // 十万の位 (10^5) n[5] = 6 // 百万の位 (10^6)
2 < 3
のとき初めて数が小さくなります。このときn[3] < n[2]
なので、i = 3
です。
③n[0]
からn[i-1]
まで順番に見ていき、n[i]
より初めて大きくなるものを求めます。求めたものをn[j]
とします。
2
より下の桁で2
より大きい数で、その中で最小なのは3
です。3
は2つありますが、桁が小さい方を選択します。桁が小さい方は
n[1] = 3
なので、j = 1
です。
④n[i]
とn[j]
を入れ替えます
3
と2
を入れ替えます。
⑤n[0]
からn[i-1]
を逆順にします
以上で、652331
から、次に大きい数である、653123
を得ることができました。
応用 : n個の数のうちk個を使用する組み合わせ
上記のアルゴリズムは、n個の数を全て使用する場合の順列を列挙しました。 n個の数のち、k個を使用する場合のアルゴリズムは以下をご覧ください。
★記事作成中
Groovyのクロージャ ④Groovyで独自のDSLの作成
背景
JenkinsというCIツールではGroovyのコードでCI挙動を記述できるJenkins pipelineがあります。 ここではGroovyのDSL(Domain-Specific Language:ドメイン固有言語)が使われています。 DSLにはクロージャが効果的に使用されています。
今回は独自のDSLの作成です。
前回の記事
前回の記事で、 クロージャの名前解決の方法の各挙動を確認しました。
今回は、クロージャと名前解決方法を利用して、独自のDSLを定義します。
DSLとは
DSLとは特定のタスク向けに設計されたコンピュータ言語である。
例えば、文章の構造を表すDSL(XMLなど)やページの装飾に特化したDSL(CSSなど)、データの取得に特化したDSL(SQLなど)が挙げられます。
特定のタスクに向けて設計されるDSLは、プログラミング経験者以外が使用することを前提としたものもあります。また、人が自然に読めるように配慮されているものも多くあります。
記述には、宣言型のスタイルがよく用いられます。 宣言型のスタイル(宣言型プログラミング)とは、
対象の性質を宣言してプログラムを構成するプログラミングパラダイム、あるいはそのような性質をもったプログラミングパラダイムの総称である。
宣言型プログラミングでは、どのように処理をするかは書かれておらず、何を処理するか(対象)を記述(宣言)します。
例: SQLの場合
SELECT id, name, price FROM item WHERE price >= 100 -- itemテーブルからpriceが100以上の行を見つけ、その行のidとnameとpriceを取得するという意味のSQL -- 具体的にどのように取ってくるかは書かれていない
GroovyでのDSLの実現方法
Groovyでは以下のようなDSLを作成できます。何を表すか(するか)という短い説明の後に、内容を記載します。
子要素がある場合は{
と}
で囲います。
report { title "DSLの説明" date "2020-02-03" body { section("クロージャとは") { paragraph "クロージャとは生まれ故郷(クロージャ自身が定義された場所)を忘れない無名関数のことです。" } section("thisとownerとdelegate") { paragraph "thisはクロージャを囲んでいるクラスです。" paragraph "ownerはクロージャを囲んでいるオブジェクトです。クラスか、クロージャを囲んでいるクロージャです。" paragraph "delegateは外部のオブジェクトです。メソッドやプロパティ名が元のオブジェクトで解決できないときに呼ばれます。" } } }
この記法はプログラミング言語っぽくないですが、groovyの言語仕様に従って記載されています。{
と}
で囲まれた部分はクロージャです。report
やtitle
、section
などはメソッドです。
今回は以下のような簡単なDSLを作成します。
- reportディレクティブはレポートを作成するためのトップ階層です
- reportの下にはtitle、date、bodyのみ記載することができます
- title、dateには文字列を続けて書きます
- bodyの子要素はsectionのみです
- sectionの子要素はparagraphのみです
- paragraphには文字列を続けて書きます
reportメソッドの作成
report
メソッドは以下のようになります。クロージャのdelegate
にReportSpec
クラスのインスタンスを指定し、resolveStrategy
をClosure.DELEGATE_ONLY
に設定します。
def report(Closure cl) { cl.delegate = new ReportSpec() cl.resolveStrategy = Closure.DELEGATE_ONLY cl() }
移譲先のクラスの作成
ReportSpec
クラスです。title
メソッドとdate
メソッドは対応する文字列を表示します。body
メソッドは、クロージャを引数にとり、BodySpec
クラスのインスタンスをdelegate
に設定しています。
class ReportSpec { void title(String title) { println "<h1>${title}</h1>"} void date(String date) { println "<div>作成日 : ${date}</div>"} void body(Closure body) { body.delegate = new BodySpec() body.resolveStrategy = Closure.DELEGATE_ONLY body() } }
同様に、BodySpec
は、以下です。
class BodySpec { void section(String title, Closure section) { println "<h2>${title}</h2>" section.delegate = new SectionSpec() section.resolveStrategy = Closure.DELEGATE_ONLY section() } }
同様に、SectionSpec
は、以下です。
class SectionSpec { void paragraph(String paragraph) {println "<p>${paragraph}</p>"} }
実行結果
以下のDSLを実行します。
report { title "DSLの説明" date "2020-02-03" body { section("クロージャとは") { paragraph "クロージャとは生まれ故郷(クロージャ自身が定義された場所)を忘れない無名関数のことです。" } section("thisとownerとdelegate") { paragraph "thisはクロージャを囲んでいるクラスです。" paragraph "ownerはクロージャを囲んでいるオブジェクトです。クラスか、クロージャを囲んでいるクロージャです。" paragraph "delegateは外部のオブジェクトです。メソッドやプロパティ名が元のオブジェクトで解決できないときに呼ばれます。" } } }
実行結果です。
<h1>DSLの説明</h1> <div>作成日 : 2020-02-03</div> <h2>クロージャとは</h2> <p>クロージャとは生まれ故郷(クロージャ自身が定義された場所)を忘れない無名関数のことです。</p> <h2>thisとownerとdelegate</h2> <p>thisはクロージャを囲んでいるクラスです。</p> <p>ownerはクロージャを囲んでいるオブジェクトです。クラスか、クロージャを囲んでいるクロージャです。</p> <p>delegateは外部のオブジェクトです。メソッドやプロパティ名が元のオブジェクトで解決できないときに呼ばれます。</p>
レポートが作成されました。
rehydrateメソッドの使用
今回、report
, reportSpec
, BodySpec
内で、クロージャのdelegate
を以下のように指定しました。
def report(Closure cl) { cl.delegate = new ReportSpec() cl.resolveStrategy = Closure.DELEGATE_ONLY cl() }
一般的に、引数として受け取った変数の内容は変更すべきではありません。
今回は引数として受け取ったクロージャのdelegate
フィールドを書き換えていたので、この制約を破っています。
この状態を避けるために、クロージャをコピーし、コピーしたものに対してdelegate
を変更します。
幸いなことに、コピーとdelegate
の変更を一度に行うrehydrate
というメソッドが用意されています。
(hydrateは水分を補給するという意味)
rehydrate
ではクロージャをコピーして、owner
とthis
とdelegate
を引数で与えられたオブジェクトに変更したものを返します。
report
メソッドをrehydrate
で書き換えます。owner
とthisObj
の部分にthis
を指定していますが、下で名前解決方法をClosure.DELEGATE_ONLY
に指定しているので、owner
とthis
の部分は何でも構いません。
def report(Closure cl) { def reportSpec = new EmailSpec() def clCopy = cl.rehydrate(reportSpec, this, this) clCopy.resolveStrategy = Closure.DELEGATE_ONLY clCopy() }
以上で独自のDSLの作成できました。
参考リンク
The Apache Groovy programming language - Domain-Specific Languages
Groovyのクロージャ ③名前解決方法(resolveStrategy)の挙動
背景
JenkinsというCIツールではGroovyのコードでCI挙動を記述できるJenkins pipelineがあります。 Jenkins pipelineではGroovyのDSL(Domain-Specific Language:ドメイン固有言語)が使われています。 DSLにはクロージャが効果的に使用されています。
今回はクロージャの名前解決方法(resolveStrategy)です。
前回の記事
前回の記事で、
クロージャは故郷を忘れないためにthis
とowner
に生まれた場所の情報を格納していることが確認できました。また、クロージャで呼んでいるメソッドがowner
で定義されていない場合にdelegate
のメソッドを呼ぶことが分かりました。
名前解決とは
名前解決とは、ここでは、「メソッドやプロパティ名が現れたとき、どこに定義されている名前を使用するか決めること」とします。
クロージャの名前解決 (resolveStrategy)
クロージャは、内部で呼んでいるメソッドがowner
で定義されていない場合にdelegate
のメソッドを呼びます。この挙動はクロージャオブジェクトのresolveStrategy
プロパティに値をセットすることで変更できます。セットできるのは以下の5つです。
名前解決方法 | 説明 |
---|---|
Closure.OWNER_FIRST | デフォルト。プロパティ/メソッドがownerに存在するときは、ownerのものを使用し、なければdelegateのものを使用する |
Closure.DELEGATE_FIRST | OWNER_FIRSTの逆。プロパティ/メソッドがdelegateに存在するときは、delegateのものを使用し、なければownerのものを使用する |
Closure.OWNER_ONLY | プロパティ/メソッドの名前解決をownerのみで行う。delegateは無視される |
Closure.DELEGATE_ONLY | プロパティ/メソッドの名前解決をdelegateのみで行う。ownerは無視される |
Closure.TO_SELF | 名前解決はクロージャクラスで行われる。開発者がクロージャのサブクラスを作成して、クロージャの振る舞いをカスタマイズしたい場合にこの設定にする |
名前解決方法の挙動の確認
OWNER_FIRST
、DELEGATE_FIRST
、OWNER_ONLY
、DELEGATE_ONLY
の動作を確認するため、Main
クラスとPipelineSpec
クラスそれぞれに以下のようにメソッドを定義します。
a() | b() | c() | |
---|---|---|---|
Main | ○ | ○ | × |
PileineSpec | × | ○ | ○ |
class PipelineSpec { def b() { println "I'm PipelineSpec.b" } def c() { println "I'm PipelineSpec.c" } } class Pipeline { def pipeline(Closure cl) { cl.delegate = new PipelineSpec() // ここを書き換えててテストする cl.resolveStrategy = Closure.OWNER_FIRST println "before closure" cl() println "after closure" } } class Main { // 普通のインスタンスメソッド def closureTest() { def pipeline = new Pipeline() pipeline.pipeline { a() b() c() } } def a() { println "I'm Main.a" } def b() { println "I'm Main.b" } } def main = new Main() main.closureTest()
OWNER_FIRST
上記のコードを実行した結果です。
before closure I'm Main.a I'm Main.b I'm PipelineSpec.c after closure
a()
メソッドとb()
メソッドはMain
クラスに定義したものが呼ばれ、c()
メソッドはPipelineSpec
のものが呼ばれました。
DELEGATE_FIRST
上記コードを下記のように書き換えて実行します。
// ここを書き換えててテストする
cl.resolveStrategy = Closure.DELEGATE_FIRST
実行結果です。
before closure I'm Main.a I'm PipelineSpec.b I'm PipelineSpec.c after closure
a()
メソッドはMain
クラスに定義したものが呼ばれ、b()
メソッドとc()
メソッドはPipelineSpec
のものが呼ばれました。
OWNER_ONLY
上記コードを下記のように書き換えて実行します。
// ここを書き換えててテストする
cl.resolveStrategy = Closure.OWNER_ONLY
実行結果です。
before closure I'm Main.a I'm Main.b Exception thrown groovy.lang.MissingMethodException: No signature of method: Main.c() is applicable for argument types: () values: [] Possible solutions: a(), b(), is(java.lang.Object), any(), tap(groovy.lang.Closure), any(groovy.lang.Closure) at Main$_closureTest_closure1.doCall(closure_01.groovy:27) at Main$_closureTest_closure1.doCall(closure_01.groovy) // 以下略
Main
クラスに定義したa()
メソッドとb()
メソッドが呼ばれたあと、名前解決が失敗し、MissingMethodException
が発生しました。
PipelineSpec
での名前解決が行われなかったことがわかります。
DELEGATE_ONLY
上記コードを下記のように書き換えて実行します。
// ここを書き換えててテストする
cl.resolveStrategy = Closure.DELEGATE_ONLY
実行結果です。
before closure Exception thrown groovy.lang.MissingMethodException: No signature of method: PipelineSpec.a() is applicable for argument types: () values: [] Possible solutions: b(), c(), any(), tap(groovy.lang.Closure), any(groovy.lang.Closure), is(java.lang.Object) at Main$_closureTest_closure1.doCall(closure_01.groovy:25) at Main$_closureTest_closure1.doCall(closure_01.groovy) // 以下略
a()
メソッドが見つからず、MissingMethodException
が発生しました。Main
メソッドでの名前解決が行われなかったことがわかります。
DELEGATE_FIRSTとDELEGATE_ONLYの使いどころ
DELEGATE_FIRST
とDELEGATE_ONLY
は、時に使用者の意図しない挙動を引き起こします。
例えば、以下のように、closureTest
メソッド内でpipeline
メソッドに渡しているクロージャでa()
を呼び出したとき、Main
クラスの実装者はMain
クラスのa()
を呼ぶことを意図していますが、実際にはPipelineSpec
クラスのa()
メソッドが呼ばれてしまいます。これはバグの温床になりそうです。
class PipelineSpec { def a() { println "I'm PipelineSpec.a" } } class Pipeline { def pipeline(Closure cl) { cl.delegate = new PipelineSpec() cl.resolveStrategy = Closure.DELEGATE_FIRST println "before closure" cl() println "after closure" } } class Main { def closureTest() { def pipeline = new Pipeline() pipeline.pipeline { // Main#a()を呼ぶ意図で書いているのに、実際にはPipelineSpec#a()が呼ばれる a() } } def a() { println "I'm Main.a" } } def main = new Main() main.closureTest()
DELEGATE_ONLYの使い所は、DSL(Domain-Specific Language)です。 DELEGATE_ONLYでは、クロージャ内から呼び出せるメソッドを制限することができます。 次回の記事で詳しく解説します。
参考リンク
The Apache Groovy programming language - Closures
環境
次回に続く
Groovyのクロージャ ②クロージャのthisとownerとdelegate
背景
JenkinsというCIツールではGroovyのコードでCI挙動を記述できるJenkins pipelineがあります。 Jenkins pipelineではGroovyのDSL(Domain-Specific Language:ドメイン固有言語)が使われています。 DSLにはクロージャが効果的に使用されています。
今回はクロージャのthisとownerとdelegateです。
前回の記事
前回の記事で、 クロージャとは生まれ故郷(クロージャ自身が定義された場所)を忘れない無名関数のこと、 クロージャは、クロージャが定義された場所で動く(ように見える)、ということが確認できました。
クロージャが故郷を忘れないためにしていること
クロージャが実行されたときどのようなことが起こっているのでしょうか。どのようにして元のクラスのメソッドを呼ぶのでしょうか。
その答えは、クロージャが故郷(クロージャが定義された場所)の情報を持っているからです。
クロージャはオブジェクトなので、内部に情報を持てます。クロージャのインスタンス変数にはthis
、owner
、delegate
の3つが定義されています。
それぞれ以下の情報が入っています。
フィールド | 入ってる情報 |
---|---|
this | クロージャを囲んでいるクラス |
owner | クロージャを囲んでいるオブジェクト。クラスか、クロージャを囲んでいるクロージャ |
delegate | 外部のオブジェクト。メソッドやプロパティ名が元のオブジェクトで解決できないときに呼ばれる |
確認してみましょう。
class Main { // 普通のインスタンスメソッド def closureTest() { Closure cl = { a() } println "this : ${cl.thisObject}" println "owner : ${cl.owner}" println "delegate : ${cl.delegate}" } def a() { println "I'm Main.a" } } def main = new Main() main.closureTest()
実行結果です。
this : Main@2e654c59 owner : Main@2e654c59 delegate : Main@2e654c59
すべてMainクラスのインスタンスという結果でした。クロージャの中にさらにクロージャがある場合(クロージャがネストしている場合)にはownerとdelegateの値が、対象のクロージャを囲むクロージャになります。詳しくはこちらを参照してください。
ここまでで、クロージャは故郷を忘れないためにthis
とowner
に生まれた場所の情報を格納していることが分かりました。
delegate
は、デフォルトではowner
と同じですが、クロージャが名前解決に使用するオブジェクトを格納するために使用されます。
delegateにクラスを指定する
delegate
にクラスを指定します(正確にいうと、クラスのインスタンスを指定します)。Pipelineクラスのpipeline()
メソッド内で、クロージャのdelegate
を変更します。
PipelineSpecクラスにa()
メソッドを定義しました。Mainクラスにはa()
メソッドはありません。
class PipelineSpec { def a() { println "I'm PipelineSpec.a" } } class Pipeline { def pipeline(Closure cl) { cl.delegate = new PipelineSpec() println "before closure" cl() println "after closure" } } class Main { def closureTest() { def pipeline = new Pipeline() pipeline.pipeline { a() } } } def main = new Main() main.closureTest()
実行結果です。
before closure I'm PipelineSpec.a after closure
クロージャcl
内のa()
メソッドは、PipelineSpecのa()
メソッドを呼んでいます。
このように、owner
のオブジェクトに該当するメソッドがない場合は、delegate
に指定されたオブジェクトのメソッドを実行します。
環境
参考リンク
次回に続く
Groovyのクロージャ ①クロージャ内のメソッド呼び出し基礎編
背景
JenkinsというCIツールではGroovyのコードでCI挙動を記述できるJenkins pipelineがあります。 Jenkins pipelineではGroovyのDSL(Domain-Specific Language:ドメイン固有言語)が使われています。 DSLにはクロージャが効果的に使用されています。
今回はクロージャの動作の基本編です。
クロージャとは
クロージャとは、生まれ故郷(クロージャ自身が定義された場所)を忘れない無名関数のことです。
こちらページが詳しいです。
クロージャ内のメソッド呼び出し
生まれ故郷を忘れない無名関数とは何か、以下のプログラムで確認します。
MainクラスのclosureTest()
内でPilpeline
クラスのpipeline
関数にクロージャ({
と}
で囲んだ部分)を渡しています。
(クラス名と関数名はJenkins pipelineを意識しています)
クロージャの内部ではa()
を呼び出しています。a()
はMain
クラス、Pipeline
クラス両方で定義されています。
pipeline()
メソッド内で、渡されたクロージャ(cl
)を実行しています。
class Pipeline { def pipeline(Closure cl) { println "before closure" cl() println "after closure" } def a() { println "I'm Pipeline.a" } } class Main { def closureTest() { def pipeline = new Pipeline() pipeline.pipeline { a() } } def a() { println "I'm Main.a" } } def main = new Main() main.closureTest()
このコードを実行します。出力は以下のようになりました。
before closure I'm Main.a after closure
クロージャが実行されたとき、Main.a()
が呼ばれていることがわかります。
このように、クロージャは呼ばれた場所でなく、定義された(クロージャが書かれた)場所で実行されます。難しくいうと、クロージャは変数名やメソッドの名前解決を、(デフォルトでは)定義された場所で行う、ということです。クロージャを実行する側(今回はPipelineクラス)での名前解決は行われません。
呼び出し元のメソッドは呼ばれるか
確認として、Main.a()
を削除してみましょう。それ以外は上記と同じコードです。
class Pipeline { def pipeline(Closure cl) { println "before closure" cl() println "after closure" } def a() { println "I'm Pipeline.a" } } class Main { def closureTest() { def pipeline = new Pipeline() pipeline.pipeline { a() } } // def a() { // println "I'm Main.a" // } } def main = new Main() main.closureTest()
実行します。エラーになりました。
before closure Exception thrown groovy.lang.MissingMethodException: No signature of method: Main.a() is applicable for argument types: () values: [] Possible solutions: any(), tap(groovy.lang.Closure), any(groovy.lang.Closure), is(java.lang.Object), wait(), wait(long) at Main$_closureTest_closure1.doCall(closure_01.groovy:18) at Main$_closureTest_closure1.doCall(closure_01.groovy) at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method) at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62) at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43) at Pipeline.pipeline(closure_01.groovy:4) at Pipeline$pipeline.call(Unknown Source) at Main.closureTest(closure_01.groovy:17) at Main$closureTest.call(Unknown Source) at closure_01.run(closure_01.groovy:36) at jdk.internal.reflect.GeneratedMethodAccessor60.invoke(Unknown Source) at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
これにより、クロージャを実行したクラス/メソッド(今回はPipeline.pipeline()
)に定義されたメソッドはクロージャ内からは呼ばれないことが分かりました。
環境
次回に続く
「ピーターからの問題」1から9までを使って分数の穴埋め算。解答のJavaScriptプログラム
Qiitaでこちらの問題をみたので、解いてみました。
これをjsで解けと会社の上司に言われたんですが全然わからん。
— ケイセイ@JavaScriptと仲良くなりたい (@keisei_otsuka) 2020年2月2日
誰かわかります?笑 pic.twitter.com/ZM6VmigaVQ
アルゴリズム
考えることは大きく分けて以下の2つです。
- 1から9を1回ずつ使った組み合わせを列挙する
- 分数を計算して1かどうか確かめる
1から9を1回ずつ使った組み合わせを列挙する
こちらのアルゴリズムを利用して、1から9を1回ずつ使った組み合わせを列挙します。
分数を計算して1かどうか確かめる
今回、分数の計算が必要に思えますが、式を以下のように変形すれば、分数を使わずとも解けることがわかります。
a/x + b/y + c/z = 1
// ↓
a*y*z + b*x*z + c*x*y = x*y*z
下準備
各マスに番号をふっておきます。配列のインデックスに対応します。
1から9までの数字を格納している配列をn
とすると、解く式は以下のように書けます。
n[0]/(n[1] * 10 + n[2]) + n[3]/(n[4] * 10 + n[5]) + n[6]/(n[7] * 10 + n[8]) = 1
コード
/** * 配列の順列を列挙するジェネレータ */ function* arrayEnumerator(numArr){ yield [...numArr] while(true) { // numArr[i] < numArr[i-1] となるiを探す const changeIndex1 = numArr.findIndex((value, i , arr) => i >=1 && arr[i-1] > value) if (changeIndex1 < 0) { break } const changeNumber1 = numArr[changeIndex1] const newOrderArr = numArr.slice(0, changeIndex1) // changeNumber1 より下位の桁で、changeNumber1 より大きい数字のうち、最小のものを探す const changeNumber2 = Math.min(...newOrderArr.filter(value => value > changeNumber1)) const changeIndex2 = newOrderArr.indexOf(changeNumber2) // changeNumber1とchangeNumber2入れ替える // 下位桁はreverseする newOrderArr[changeIndex2] = changeNumber1 numArr = [...newOrderArr.reverse(), changeNumber2, ...numArr.slice(changeIndex1 + 1)] yield [...numArr] } } const enumerator = arrayEnumerator([9, 8, 7, 6, 5, 4, 3, 2, 1]) for(let n of enumerator){ // denominators(分母) const denomi = [10 * n[1] + n[2], 10 * n[4] + n[5], 10 * n[7] + n[8]] // 左辺 const left = n[0] * denomi[1] * denomi[2] + n[3] * denomi[0] * denomi[2] + n[6] * denomi[0] * denomi[1] // 右辺 const right = denomi.reduce((acc, cur) => acc * cur , 1) if (left === right) { console.log(`${n[0]}/${n[1]}${n[2]} + ${n[3]}/${n[4]}${n[5]} + ${n[6]}/${n[7]}${n[8]} equals to 1`) break } }
あとがき
急いで書いたので、変数名が微妙になってしまいました。
JavaScriptでPython風のzip_longest関数を実装する
こちらの記事でPython風のzip関数を実装しました。
今回はzip_longest
関数を作成します。以下のように、各配列の同じインデックスの要素をまとめます。
const a1 = [1, 2, 3] const a2 = ["Jan", "Feb", "Mar"] const a3 = ["Garnet", "Amethyst", "Aquamarine"] zip_longest(a1, a2, a3) #=> [[1, "Jan", "Garnet"], [2, "Feb", "Amethyst"], [3, "Mar", "Aquamarine"]]
各配列の長さが異なる場合には、一番長い配列の長さになります。未定義値はundefined
になります。
const a1 = [1, 2, 3, 4] const a2 = ["Jan", "Feb", "Mar", "Apr", "May"] const a3 = ["Garnet", "Amethyst", "Aquamarine"] zip_longest(a1, a2, a3) #=> [[1, "Jan", "Garnet"], [2, "Feb", "Amethyst"], [3, "Mar", "Aquamarine"], [4, "Apr", undefined], [undefined, "May", undefined]]
zip_longest関数本体
zip_longest関数の実装です。
const zip_longest = (...arrays) => { const length = Math.max(...(arrays.map(arr => arr.length))) return new Array(length).fill().map((_, i) => arrays.map(arr => arr[i])) }
コードの解説
ほとんどzip
関数の解説と同じです。
まず、関数の定義の部分を解説します。レスト構文を使用して、引数全てをarrays
に格納します。
const zip_longest = (...arrays) => { }
例えば、
const a1 = [1, 2, 3, 4] const a2 = ["Jan", "Feb", "Mar", "Apr", "May"] const a3 = ["Garnet", "Amethyst", "Aquamarine"] zip_longest(a1, a2, a3)
と呼び出したとき、arrays
は
[ [1, 2, 3, 4], ["Jan", "Feb", "Mar", "Apr", "May"], ["Garnet", "Amethyst", "Aquamarine"] ]
です。以下、引数にこの配列を渡したときの動作を説明します。
zip_longest
関数では、一番長い配列の長さに合わせるので、まず一番長い配列の長さを求めます。
まず、各配列の長さを、求めます。
const zip_longest = (...arrays) => { arrays.map(arr => arr.length) #=> [4, 5, 3] }
この中の最大値は、Math.maxとスプレッド演算子を使用して、以下のように書けます。
const zip_longest = (...arrays) => { const length = Math.max(...(arrays.map(arr => arr.length))) #=> const length = Math.max(...[4, 5, 3]) #=> const length = Math.max(4, 5, 3) #=> const length = 5 }
5回繰り返すので、new Array(length).fill().map((_, i) => i)
の構文を使用します。
const zip_longest = (...arrays) => { const length = Math.max(...(arrays.map(arr => arr.length))) new Array(length).fill().map((_, i) => i)) #=> [0, 1, 2, 3, 4] }
fill
をはさむ理由については、こちらの記事をご覧ください。
各配列のi
番目の要素は、
arrays.map(arr => arr[i])
で取得することができます。よくわからない場合は、i
ではなく、0
、1
、2
など具体的な数字で考えるとよいです。例えば、各配列の0番目の要素は、
arrays.map(arr => arr[0]) #=> [1, "Jan", "Garnet"]
です。
これをmap
に渡す関数の戻り値にします。
JavaScriptの場合、配列の長さより大きいインデックスを指定した場合はundefined
になります。
const zip_longest = (...arrays) => { const length = Math.max(...(arrays.map(arr => arr.length))) return new Array(length).fill().map((_, i) => arrays.map(arr => arr[i])) #=> [[1, "Jan", "Garnet"], [2, "Feb", "Amethyst"], [3, "Mar", "Aquamarine"], [4, "Apr", undefined], [undefined, "May", undefined]] }
以上でzip_longest
関数の完成です。
補足的な話題はzip関数の方の記事に記載していますので、あわせてご覧ください。