１．はじめに

結論

　異なる $ N $ 個の自然数から重複を許さずに $ R $ 個選んだときの、全組合せのリストを生成するクラスを作成した（詳細は「３．実装」参照）。このクラスを呼び出すことにより、たとえば $ {}_{37} \mathrm{C}_7 = 10,295,472 $ 通りのリストを生成することができる（メモリオーバーにならない限り）。
　また、事前に組合せを求めたい対象のインデックスの全組合せリストを生成するため、自然数以外にも文字列などの組合せリストを生成できるよう応用することもできる。

お断り

　筆者は最近JavaからTypeScriptに乗り換え、かつJavaScriptはかじった程度であるため、書き方がJava寄りになっているかも知れない。また、TypeScriptの学習が第一目的であるため、そもそもTypeScriptで実装する必要がないことをわざわざTypeScriptで記述している可能性もある。

ロト７について

　ロト７は $ 37 $ 個の数字から $ 7 $ 個の数字を選ぶ宝くじである。選んだ数字が抽せん結果と何個一致したかにより、１等から６等までの当せんパターンが存在する。なお、１等かつキャリーオーバーの場合、当せん金額は__10億円__になる（超重要）。

２．設計

要件

　筆者はロト７の全当せんパターンの当せんしやすさを評価するアプリを作成しようと考えており、そのためにまずはロト７の全当せんパターンを生成するクラスを作成することにした。また、場合によっては全パターンを生成する必要はなく、当せんパターンに必ず含める数字、または含めない数字があることも考えられるため、そのような要求にも応えられるようにした。

方針

　問題を分割するため、まず組合せを求めたい対象のインデックスに対し、すべての組合せのリストを生成するクラス（Combination Index ListsGeneratorクラス）を作成する。
　次に、組合せ対象の各要素をインデックスと置き換えることにより、自然数の全組合せリストを生成するクラス（Combination NaturalNumber ListsGeneratorクラス）を作成する。本記事では割愛するが、このクラスを流用すれば文字列の全組合せリストを生成するクラス（CombinationStringListsGeneratorクラス？）を作成することも可能と考えられる。

課題１：ループ処理の汎用化（CombinationIndexListsGeneratorクラス）

　インデックスの全組合せリストを生成するにあたり、たとえば選ばれる個数が $ 7 $ 個と分かっている状況であれば、下記のようにループ処理を $ 7 $ 個組み合わせる方法が考えられる。

sample1.ts

const indexesList: number[][] = []
for (let a = 0; a < 37; a++) {
  for (let b = a + 1; b < 37; b++) {
    for (let c = b + 1; c < 37; c++) {
      for (let d = c + 1; d < 37; d++) {
        for (let e = d + 1; e < 37; e++) {
          for (let f = e + 1; f < 37; f++) {
            for (let g = f + 1; g < 37; g++) {
              const indexes: number[] = []
              indexes.push(a)
              indexes.push(b)
              indexes.push(c)
              indexes.push(d)
              indexes.push(e)
              indexes.push(f)
              indexes.push(g)
              indexesList.push(indexes)
            }
          }
        }
      }
    }
  }
}

　しかし、筆者は将来的にミニロト（ $ 5 $ 個選択）やロト６（ $ 6 $ 個選択）にも本プログラムを流用しようと考えているため、そのたびにループ処理の実装が異なることは避けたい。

　そこで、当せんパターンの各数字をＮ進数に置き換えることにより、ループ処理を１個にまとめることにした。たとえばロト７の場合、選ばれる対象は $ 1 $ から $ 37 $ までの $ 37 $ 個の自然数であり、これらの数字をそれぞれインデックス $ 0 $ ～ $ 36 $ に置き換える。そして、各当せんパターンをＮ進数に置き換える。最初のループのインデックス $ [ 0, 1, 2, 3, 4, 5, 6 ] $ の場合、そのＮ進数（37進数）は $ 123456_{(37)} $ となり、それを10進数に変換すると、

0 \times 37^6 + 1 \times 37^5 + 2 \times 37^4 + 3 \times 37^3 + 4 \times 37^2 + 5 \times 37^1 + 6 \times 37^0
\\ = 73,249,905

となる。また、最後のループのインデックスは $ [ 30, 31, 32, 33, 34, 35, 36 ] $ となり、それを10進数に変換すると

30 \times 37^6 + 31 \times 37^5 + 32 \times 37^4 + 33 \times 37^3 + 34 \times 37^2 + 35 \times 37^1 + 36 \times 37^0
\\ = 79,183,147,515

となる。これらにより、上述のループ処理は次のように簡略化（？）できる。

sample2.ts

const indexesList: number[][] = []
for (let loopCounter = 73249905; loopCounter <= 79183147515; loopCounter++) {
  // todo: 昇順・重複の除外（課題２参照）
  // todo: loopCounterを10進数に置き換え、各位の数字をindexesに格納する
  indexesList.push(indexes)
}

課題２：昇順・重複の除外（CombinationIndexListsGeneratorクラス）

　上述のsample2.tsでは、単にループを回すだけだと下記のようなケースが存在してしまう。

インデックスが昇順でないもの（例：$ [ 0, 1, 2, 6, 5, 4 ] $）
インデックスが重複しているもの（例：$ [ 0, 1, 2, 3, 3, 3 ] $）

仮にこれらを判定・除外できたとしても、そもそも対象外のインデックスに対してもループが回ってしまうことは、処理効率の観点からも避けたい。単純計算でも、ループ回数 $ 79183147515 - 73249905 + 1 = 79,109,897,611 $ 回のうち、組合せ対象は $ {}_{37} \mathrm{C}_7 = 10,295,472 $ 回（$ 0.01 $％！）しかないのである。

解決案：Ｎ進数の繰上り処理の改善（CombinationIndexListsGeneratorクラス）

　そもそもインデックスの昇順が崩れたり、重複が発生したりする原因はＮ進数の繰上りにある。たとえば $ [ 0, 1, 2, 3, 4, 5, 36 ] $ の次のループのインデックスは、繰上りが発生するため $ [ 0, 1, 2, 3, 4, 6, 0 ] $ となるのであるが、この時に昇順崩れや重複が発生してしまっている。ここで昇順崩れや重複が発生した部分に注目すると、これらは必ず繰上りの影響を受ける桁にだけ限定されている（上記のケースだと下 $ 2 $ 桁）。本来、正しい組合せの対象としては、次のインデックスは $ [ 0, 1, 2, 3, 4, 6, 7 ] $ が来るべきであって、要は $ [ 0, 1, 2, 3, 4, 5, 36 ] $ の次は自動的に $ [ 0, 1, 2, 3, 4, 6, 7 ] $ が来るような繰上り処理を実装すれば、インデックスの昇順崩れや重複は発生しないのである。

　そこで、繰上り時の処理を以下のように実行するようにした。ただし、「$ m $桁目」とはＮ進数に置き換えたときの最上位から数えて $ m $ 桁目、つまりインデックスとしては左から $ m $ 個目の数字という意味である。

$ m $ 桁目が繰り上がる場合、次のようなインデックスを生成できるかどうか判定する。
$ m $ 桁目以降の数字はすべて $ m - 1 $ 桁目から $ 1 $ ずつ大きくなっていること。
最後の桁はインデックスの最大値以下である。
上記を満たすインデックスを生成できる場合は、生成する。生成できない場合は、代わりに $ m - 1 $ 桁目に対して同様に判定を行い、以後上記を満たすインデックスを生成できない場合は $ m - 2 $ 桁目、$ m - 3 $ 桁目というように、繰上り対象の桁を１つずつ左にずらしていく。

上記を実装すると、次の通りとなる。変数shouldCarryUpに判定結果が格納されており、上記を言い換えると、インデックスのとり得る最大値を $ L $、全桁数を $ M $ として、$ m - 1 $ 桁目の数字が $ L - M + (m - 1) $ 以上であれば、繰上り対象の桁を１つずつ左にずらしていく、となる。

CombinationIndexListsGenerator.ts（繰上り関連のみ）

private _getNextIndexes(indexes: number[]): number[] {
  const nextIndexes = indexes.concat()
  nextIndexes[nextIndexes.length - 1]++
  for (let i = 0; i < nextIndexes.length - 1; i++) {
    const shouldCarryUp = nextIndexes[nextIndexes.length - 1 - i] >= this._maxIndex + 1 - i
    if (shouldCarryUp) this._carryUp(nextIndexes, nextIndexes.length - 2 - i)
  }
  return nextIndexes
}

private _carryUp(indexes: number[], target: number): void {
  indexes[target]++
  for (let i = 1; i < indexes.length - target; i++) {
    indexes[target + i] = indexes[target] + i
  }
}

３．実装

　上述の方針を基に、CombinationIndexListsGeneratorクラスとCombinationNaturalNumberListsGeneratorクラス、ならびに順列と組合せの総数をそれぞれ計算するcalcPermutationmメソッド、calcCombinationメソッドを下記のように実装した。

CombinationIndexListsGenerator.ts

CombinationIndexListsGenerator.ts

import { calcCombination } from '@/logics/math/calcCombination'

export class CombinationIndexListsGenerator {
  private _maxIndex: number
  private _length: number
  private _indexLists: number[][]

  /**
   * 0以上maxIndex以下の整数から重複を許さずlength個を選んだときの、全組合せ(昇順)のリストを作成する。
   * ただし、maxIndex + 1 >= length > 0でない場合は空のリストを返す。
   * @param maxIndex インデックスの最大値
   * @param length 各リストの要素数
   */
  constructor(maxIndex: number, length: number) {
    this._maxIndex = maxIndex
    this._length = length
    this._indexLists = []
  }

  get indexLists(): number[][] {
    return this._indexLists
  }

  public getIndexListsLength(): number {
    return this._isCorrectParameters() ? this._calcIndexListsLength() : 0
  }

  public generate(): void {
    if (!this._isCorrectParameters()) return

    const indexListsLength = this._calcIndexListsLength()
    let indexes = this._getFirstIndexes()
    this._indexLists = []
    for (let i = 0; i < indexListsLength; i++) {
      this._indexLists.push(indexes)
      indexes = this._getNextIndexes(indexes)
    }
  }

  private _isCorrectParameters(): boolean {
    return this._length > 0 && this._maxIndex + 1 >= this._length
  }

  private _calcIndexListsLength(): number {
    return calcCombination(this._maxIndex + 1, this._length)
  }

  private _getFirstIndexes(): number[] {
    const indexes: number[] = []
    for (let i = 0; i < this._length; i++) {
      indexes.push(i)
    }
    return indexes
  }

  private _getNextIndexes(indexes: number[]): number[] {
    const nextIndexes = indexes.concat()
    nextIndexes[nextIndexes.length - 1]++
    for (let i = 0; i < nextIndexes.length - 1; i++) {
      const shouldCarryUp = nextIndexes[nextIndexes.length - 1 - i] >= this._maxIndex + 1 - i
      if (shouldCarryUp) this._carryUp(nextIndexes, nextIndexes.length - 2 - i)
    }
    return nextIndexes
  }

  private _carryUp(indexes: number[], target: number): void {
    indexes[target]++
    for (let i = 1; i < indexes.length - target; i++) {
      indexes[target + i] = indexes[target] + i
    }
  }
}

CombinationNaturalNumberListsGenerator.ts

CombinationNaturalNumberListsGenerator.ts

import { CombinationIndexListsGenerator } from '@/logics/math/CombinationIndexListsGenerator'

export class CombinationNaturalNumberListsGenerator {
  private _maxNumber: number
  private _length: number
  private _includedNumbers: number[]
  private _excludedNumbers: number[]
  private _numberLists: number[][]

  /**
   * maxNumber以下の自然数から重複を許さずlength個選んだときの、全組合せ(昇順)のリストを作成する。
   * ただし、includedNumbersが指定された場合、各リストの最小値は(includedNumbersの最大値 + 1)となる。
   * また、組合せが存在しない場合は空のリストを返す。
   * @param maxNumber 自然数の最大値
   * @param length 各リストの要素数
   * @param includedNumbers リストに必ず含まれる自然数
   * @param excludedNumbers リストから必ず除外される自然数
   */
  constructor(
    maxNumber: number,
    length: number,
    includedNumbers: number[],
    excludedNumbers: number[]
  ) {
    this._maxNumber = maxNumber
    this._length = length
    this._includedNumbers = includedNumbers
    this._excludedNumbers = excludedNumbers
    this._numberLists = []
  }

  get numberLists(): number[][] {
    return this._numberLists
  }

  public getNumberListsLength(): number {
    const usedNumbers = this._generateUsedNumbers()
    if (!this._isCorrectParameters(usedNumbers)) return 0

    const indexListsGenerator = new CombinationIndexListsGenerator(
      usedNumbers.length - 1,
      this._length - this._includedNumbers.length
    )
    return indexListsGenerator.getIndexListsLength()
  }

  public generate(): void {
    const usedNumbers = this._generateUsedNumbers()
    if (!this._isCorrectParameters(usedNumbers)) return

    const indexLists = this._generateIndexLists(usedNumbers)
    this._numberLists = this._generateNumberLists(usedNumbers, indexLists)
  }

  private _generateUsedNumbers(): number[] {
    const minNumber = this._includedNumbers.length ? Math.max(...this._includedNumbers) + 1 : 1
    const usedNumbers: number[] = []
    for (let i = minNumber; i <= this._maxNumber; i++) {
      if (!this._excludedNumbers.includes(i)) usedNumbers.push(i)
    }
    return usedNumbers
  }

  private _isCorrectParameters(usedNumbers: number[]): boolean {
    return this._length > 0 && this._includedNumbers.length + usedNumbers.length >= this._length
  }

  private _generateIndexLists(usedNumbers: number[]): number[][] {
    const indexListsGenerator = new CombinationIndexListsGenerator(
      usedNumbers.length - 1,
      this._length - this._includedNumbers.length
    )
    indexListsGenerator.generate()
    return indexListsGenerator.indexLists
  }

  private _generateNumberLists(usedNumbers: number[], indexLists: number[][]): number[][] {
    const numberLists: number[][] = []
    if (indexLists.length) {
      indexLists.forEach(indexes => {
        const sortedNumbers: number[] = []
        indexes.forEach(index => sortedNumbers.push(usedNumbers[index]))
        numberLists.push(this._includedNumbers.concat(sortedNumbers))
      })
    } else if (this._includedNumbers.length === this._length) {
      numberLists.push(this._includedNumbers)
    }
    return numberLists
  }
}

calcPermutation.ts

calcPermutation.ts

/**
 * 異なるＮ個から異なるＲ個を選んで１列に並べたときの、順列の総数を求める。
 * Ｎ、Ｒはともに自然数、かつＮ≧Ｒとし、そうでない場合は０を返す。
 * @param {number} n
 * @param {number} r
 * @returns {number} permutation
 */
export function calcPermutation(n: number, r: number): number {
  if (!Number.isInteger(n) || !Number.isInteger(r) || n < 1 || r < 1 || n < r) return 0
  let permutation = 1
  for (let i = n; i > n - r; i--) {
    permutation *= i
  }
  return permutation
}

calcCombination.ts

calcCombination.ts

import { calcPermutation } from '@/logics/math/calcPermutation'

/**
 * 異なるＮ個から異なるＲ個を選んだときの、組合せの総数を求める。
 * Ｎ、Ｒはともに自然数、かつＮ≧Ｒとし、そうでない場合は０を返す。
 * @param {number} n
 * @param {number} r
 * @returns {number} combination
 */
export function calcCombination(n: number, r: number): number {
  if (!Number.isInteger(n) || !Number.isInteger(r) || n < 1 || r < 1 || n < r) return 0
  const minor_r = n > r && n < 2 * r ? n - r : r
  return calcPermutation(n, minor_r) / calcPermutation(minor_r, minor_r)
}

　CombinationNaturalNumberListsGeneratorクラスのコンストラクタを下記のように呼び出せばロト７の全当せんパターンを生成することができ、そのリストはnumberListsゲッターを用いることにより取得できる。

sample3.ts

const generator = new CombinationNaturalNumberListsGenerator(37, 7, [], [])
generator.generate()
const numberLists = generator.numberLists