LoginSignup
92
81

More than 1 year has passed since last update.

@BlueSilverCat

Pythonで順列・組み合わせを求める

Last updated at Posted at 2017-08-18

はじめに

昔作った順列・組み合わせを列挙するプログラムを見たら、どういう考え方で作ったかすぐに理解できなかったので復習を兼ねて作り直してみました。
せっかくなので忘れないように記事にもしてみます。

だだし、itertoolsを使えば簡単に求められるので、この記事のプログラムに価値はありません。
そのうえ、Pythonの公式ドキュメントに順列や組み合わせを求める簡潔で美しいプログラムも載っています。
あくまで、個人の学習メモです。

Python 3.6.1で作っています。

それぞれ以下のように表記するものとします。

  • 与えられたデータ(listやtuple): data
  • データの長さ: n
  • 選ぶ数: r
  • 重複あり順列の総数: H(n,r)
  • 順列の総数: P(n,r)
  • 重複あり組み合わせの総数: Π(n,r)
  • 組み合わせの総数: C(n,r)

itertools

これから求めようとしているものは、itertoolsを使う事で求めることが出来ます。

  • 重複あり順列:
    list(itertools.product(data, repeat=r))
  • 順列:
    list(itertools.permutations(data, r))
  • 重複あり組み合わせ:
    list(itertools.combinations_with_replacement(data, r))
  • 組み合わせ:
    list(itertools.combinations(data, r))

決め打ち

まずは、単純化するために与えられたデータから3つ取り出す(r=3)の場合のみを考えてみます。

重複あり順列

重複あり順列は、

  1. 1回取り出したものを再度取り出せる
  2. 取り出した順番は、意味を成す(組を構成する要素が同じでも、順番が違えば別のものとして扱う)

というものです。
1つの組を求めるには、

  1. データから1つを取り出す
  2. 1で取り出したものを元に戻し、改めて1つ取り出す。
  3. 2で取り出したものを元に戻し、改めて1つ取り出す。

と言う処理を行います。
これを全ての組を求めるようにする為に、

  1. 1つ目の要素を求めるループ
  2. 1つ目のループの中にネストされた2つ目の要素を求めるループ
  3. 2つ目のループの中にネストされた3つ目の要素を求めるループ

というようにループの入れ子にします。
早速プログラムにしてみると以下のようになります。

result = []
for i in data:
  for j in data:
    for k in data:
      result.append([i, j, k])

リスト内包表記を使うと

result = [[i, j, k] for i in data for j in data for k in data]

と書けますが、本質的な処理にはリスト内包表記を使いません。
また、後々の事を考えて多少冗長ですが、以下のようにインデックスを求めてそれからデータ内容を得るようにします。

result = []
for i in range(len(data)):
  for j in range(len(data)):
    for k in range(len(data)):
      result.append([data[i], data[j], data[k]])

順列

順列は、

  1. 1回取り出したものを再度取り出せない
  2. 取り出した順番は、意味を成す(組を構成する要素が同じでも、順番が違えば別のものとして扱う)

というものです。
つまり、重複あり順列の処理に、1度取り出したものを再度取り出せなくした処理を追加することで求めることが出来ます。
そこで1つの組を求める処理を以下のようにします。

  1. データから1つを取り出す
  2. 1で取り出したものを除いた残りから1つ取り出す。
  3. 1-2で取り出したものを除いた残りから1つ取り出す。

あとの構造は、重複あり順列と同じで実現できます。
別の方法として、重複あり順列から重複を除くことでも求められます。
しかし、無駄になる繰り返しが多いのでこの方法は考えない事にします。

プログラムは、以下のようになります。
ここでは、一度取り出したものを除いたリストを返す関数listExcludedIndicesを定義して使っています。

def listExcludedIndices(data, indices):
  return [x for i, x in enumerate(data) if i not in indices]

result = []
for i in range(len(data)):
  for j in range(len(data) - 1):
    for k in range(len(data) - 2):
      jData = listExcludedIndices(data, [i])
      kData = listExcludedIndices(jData, [j])
      result.append([data[i], jData[j], kData[k]])

重複あり組み合わせ

重複あり組み合わせは、

  1. 1回取り出したものを再度取り出せる
  2. 取り出した順番は、意味を成さない(組を構成する要素が同じならば、順番が違っても同じものとして扱う)

というものです。
2.を詳しく考えてみます。
与えられたデータが[1,2,3,4]だった場合、[1,1,2]と[1,2,1]と[2,1,1]は同じものです。
つまり、重複あり順列と違い1を含む組を一通り求めたらそれ以降の1を含む組を求める必要がない事になります。
これを実現するにはネストされたループの開始位置をずらせば良いです。
以下のように表せると思います。

  1. 1つ目の要素を求めるループ
  2. 1つ目のループの中にネストされた2つ目の要素を求めるループ
    ただし、1つ目のループで取り出した位置からの開始とする
  3. 2つ目のループの中にネストされた3つ目の要素を求めるループ
    ただし、2つ目のループで取り出した位置からの開始とする

プログラムにしてみると以下のようになります。

result = []
for i in range(len(data)):
  for j in range(i, len(data)):
    for k in range(j, len(data)):
      result.append([data[i], data[j], data[k]])

組み合わせ

組み合わせは、

  1. 1回取り出したものを再度取り出せない
  2. 取り出した順番は、意味を成さない(組を構成する要素が同じならば、順番が違っても同じものとして扱う)

というものです。
そこで1つの組を求める処理を、順列を求めた時と同じように以下のようにし、

  1. データから1つを取り出す
  2. 1で取り出したものを除いた残りから1つ取り出す。
  3. 1-2で取り出したものを除いた残りから1つ取り出す。

重複あり組み合わせと同じようにループの位置をずらしてやれば良いです。
上記の考え方を元にプログラムにしてみます。

result = []
for i in range(len(data)):
  for j in range(i, len(data) - 1):
    for k in range(j, len(data) - 2):
      jData = listExcludedIndices(data, [i])
      kData = listExcludedIndices(jData, [j])
      result.append([data[i], jData[j], kData[k]])

ただし、重複あり組み合わせを

  1. 1つ目の要素を求めるループ
  2. 1つ目のループの中にネストされた2つ目の要素を求めるループ
    ただし、1つ目のループで取り出した位置からの開始とする
  3. 2つ目のループの中にネストされた3つ目の要素を求めるループ
    ただし、2つ目のループで取り出した位置からの開始とする

としていたのは重複を許るす為でしたので重複を許さなければ、

  1. 1つ目の要素を求めるループ
  2. 1つ目のループの中にネストされた2つ目の要素を求めるループ
    ただし、1つ目のループで取り出した位置より後からの開始とする
  3. 2つ目のループの中にネストされた3つ目の要素を求めるループ
    ただし、2つ目のループで取り出した位置より後からの開始とする

とすることが出来ます。
つまりプログラムも以下のように書き換えられます。

result = []
for i in range(len(data)):
  for j in range(i + 1, len(data)):
    for k in range(j + 1, len(data)):
      result.append([data[i], data[j], data[k]])

また、順列と重複あり順列のように、重複あり組み合わせから重複を取り除いても求める事が出来ます。

再帰を使う

上記までのプログラムは、rが固定のものでした。
このままでは使い物にならないので関数化します。
まずは、決め打ちで記述したものを再帰に変換します。
どれもn回繰り返すループをr回ネストした構造をしています。
r回のネストを再帰呼び出しで実現し、n回のループを1回の再帰呼び出しの中で実現すれば良いようです。
そして、再帰の終了条件をrが0になった場合としてやれば再帰に変換できます。

再帰版 重複あり順列

重複あり順列の場合は、一番単純で以下のようになります。
1回の呼び出しで得られた値をprogressとし、その値とrを-1したものを次の再帰呼び出しに渡しています。
rが0になったらprogressの中身をresultに保存して終了します。
実際に要素を求める関数は、初期値を与えなければいけません。
そのままでは使いづらいのでラッパー関数を定義してそれを呼び出すようにしています。

def permutationWithRepetitionListRecursive(data, r):
  if r <= 0:
    return []

  result = []
  _permutationWithRepetitionListRecursive(data, r, [], result)
  return result

def _permutationWithRepetitionListRecursive(data, r, progress, result):
  if r == 0:
    result.append(progress)
    return

  for i in range(len(data)):
    _permutationWithRepetitionListRecursive(data, r - 1, progress + [data[i]], result)

再帰版 順列

順列は、再度の取り出しを許さないものなので、その処理を追加してやれば求めることが出来ます。
重複あり順列は、dataをそのまま次の呼び出しに渡していましたが、こちらでは一度取り出したものを除いた残りを渡すようにします。

def permutationListRecursive(data, r):
  if r <= 0 or r > len(data):
    return []

  result = []
  _permutationListRecursive(data, r, [], result)
  return result

def _permutationListRecursive(data, r, progress, result):
  if r == 0:
    result.append(progress)
    return

  for i in range(len(data)):
    _permutationListRecursive(listExcludedIndices(data, [i]), r - 1, progress + [data[i]], result)

再帰版 重複あり組み合わせ

重複あり組み合わせは、開始位置を表す引数を追加してやり、その引数に現在の取り出し位置を与えて次の再帰呼び出しを行うようにします。
そのほかは、重複あり順列と違いはありません。

def combinationWithRepetitionListRecursive(data, r):
  if r <= 0:
    return []

  result = []
  _combinationWithRepetitionListRecursive(data, r, 0, [], result)
  return result

def _combinationWithRepetitionListRecursive(data, r, start, progress, result):
  if r == 0:
    result.append(progress)
    return

  for i in range(start, len(data)):
    _combinationWithRepetitionListRecursive(data, r - 1, i, progress + [data[i]], result)

再帰版 組み合わせ

組み合わせでは、現在の取り出し位置から1つ進めた位置で次の再帰呼び出しを行うようにします。

def combinationListRecursive(data, r):
  if r == 0 or r > len(data):
    return []

  result = []
  _combinationListRecursive(data, r, 0, [], result)
  return result


def _combinationListRecursive(data, r, start, progress, result):
  if r == 0:
    result.append(progress)
    return

  for i in range(start, len(data)):
    #別解 _combinationListRecursive(listExcludedIndices(data, [i]), r - 1, i, progress + [data[i]], result)
    _combinationListRecursive(data, r - 1, i + 1, progress + [data[i]], result)

ループを使う

再帰は、スタックオーバーフローが起こる可能性があり危険なので、ループを使った関数も考えてみます。
基本的に、1つの要素を求めるにr回のループが必要で、それを必要な数だけ繰り返してやれば良いことになります。
それぞれの総数は、公式で直ぐに求められるのでそれを使います。
また、以下では全て取り出す位置(インデックス)を元に解法を考えています。

ループ版 重複あり順列

n=4、r=3とすると、求めるべき重複あり順列は、以下のようなものになります。

00: 0 0 0 -> data[0] data[0] data[0]
01: 0 0 1 -> data[0] data[0] data[1]
02: 0 0 2 -> data[0] data[0] data[2]
03: 0 0 3 -> data[0] data[0] data[3]
04: 0 1 0 -> data[0] data[1] data[0]
05: 0 1 1 -> data[0] data[1] data[1]
06: 0 1 2 -> data[0] data[1] data[2]
07: 0 1 3 -> data[0] data[1] data[3]
08: 0 2 0 -> data[0] data[1] data[0]
09: 0 2 1 -> data[0] data[1] data[1]
10: 0 2 2 -> data[0] data[1] data[2]
11: 0 2 3 -> data[0] data[1] data[3]
...

重複あり順列は、r桁のn進数を求める事と同じになります。
何桁目かをdで表すと、それぞれの桁は、n進数と同じようにn**d毎にカウントアップします。
今何番目かの要素をiで表すと、iをn**dで割ってやればその桁のインデックスが分かります。
このままではデータのサイズを超えるので、それをnで割った余りとする必要があります。
プログラムは、以下のようになります。

import math

def permutationWithRepetition(n, r):
  return int(pow(n, r))


def permutationWithRepetitionList(data, r):
  length = len(data)
  total = permutationWithRepetition(length, r)
  result = []
  for i in range(total):
    element = []
    for digit in reversed(range(r)):
      element.append(data[int(i / pow(length, digit)) % length])
    result.append(element)
  return result

蛇足

ひさしぶりに重複あり順列が必要でした。
その時は、itertoolsを使いました。
後日、自力で作るならばどうするかと考えてみた時に出来たものが下記です。
上記の説明と異なりますが、こっちの方が分かりやすいかも。

別解
def pr(data, r):  # permutation with repetition
  length = len(data)
  total = length**r
  result = []
  for i in range(total):
    element = []
    quotient = i
    for _ in range(r):
      quotient, remainder = divmod(quotient, length)
      element.append(data[remainder])
    result.append(list(reversed(element)))
  return result

ループ版 順列

n=4、r=3とすると、求めるべき順列は、以下のようなものになります。

00: 0 1 2 -> data[0] data[1] data[2]
01: 0 1 3 -> data[0] data[1] data[3]
02: 0 2 1 -> data[0] data[2] data[1]
03: 0 2 3 -> data[0] data[2] data[3]
04: 0 3 1 -> data[0] data[3] data[1]
05: 0 3 2 -> data[0] data[3] data[2]
06: 1 0 2 -> data[1] data[0] data[2]
07: 1 0 3 -> data[1] data[0] data[3]
08: 1 2 0 -> data[1] data[2] data[0]
09: 1 2 3 -> data[1] data[2] data[3]
10: 1 3 0 -> data[1] data[3] data[0]
11: 1 3 2 -> data[1] data[3] data[2]
12: 2 0 1 -> data[2] data[0] data[1]
13: 2 0 3 -> data[2] data[0] data[3]
14: 2 1 0 -> data[2] data[1] data[0]
15: 2 1 3 -> data[2] data[1] data[3]
16: 2 3 0 -> data[2] data[3] data[0]
17: 2 3 1 -> data[2] data[3] data[1]
18: 3 0 1 -> data[3] data[0] data[1]
19: 3 0 2 -> data[3] data[0] data[2]
20: 3 1 0 -> data[3] data[1] data[0]
21: 3 1 2 -> data[3] data[1] data[2]
22: 3 2 0 -> data[3] data[2] data[0]
23: 3 2 1 -> data[3] data[2] data[2]

こちらも、要素の番号iと桁dから求められそうです。

まずは3桁目を考えてみます。
1から4まで全て同じ数だけ現れています。
つまり、P(n,r)をnで割れば、カウントアップする位置が分かります。

2桁目を考えます。
こちらは、3桁目で現れた数以外が出現します。
その総数は、n-1個です。
これが3桁目が同じ数の時に均等に出現します。
つまり、P(n,r)/(n*n-1)でカウントアップすることになります。

1桁目も同じように考えると、P(n,r)/(n*n-1*n-2)でカウントアップすることが分かります。

以上の考えからプログラムにしてみます。

import math
import functools
import operator

def permutation(n, r):
  if(n < r):
    return 0
  return int(math.factorial(n) / math.factorial(n - r))

def permutationList(data, r):
  length = len(data)
  total = permutation(length, r)
  result = []
  for i in range(total):
    element = []
    copyData = data[:]
    for digit in range(r):
      l = len(copyData)
      countUp = total / functools.reduce(operator.mul, range(l, length + 1))
      index = int(i / countUp) % l
      element.append(copyData.pop(index))
    result.append(element)
  return result

ループ版 重複あり組み合わせ

n=4、r=3とすると、求めるべき重複あり組み合わせは、以下のようなものになります。

00: 0 0 0 -> data[0] data[0] data[0]
01: 0 0 1 -> data[0] data[0] data[1]
02: 0 0 2 -> data[0] data[0] data[2]
03: 0 0 3 -> data[0] data[0] data[3]
04: 0 1 1 -> data[0] data[1] data[1]
05: 0 1 2 -> data[0] data[1] data[2]
06: 0 1 3 -> data[0] data[1] data[3]
07: 0 2 2 -> data[0] data[2] data[2]
08: 0 2 3 -> data[0] data[2] data[3]
09: 0 3 3 -> data[0] data[3] data[3]
10: 1 1 1 -> data[1] data[1] data[1]
11: 1 1 2 -> data[1] data[1] data[2]
12: 1 1 3 -> data[1] data[1] data[3]
13: 1 2 2 -> data[1] data[2] data[2]
14: 1 2 3 -> data[1] data[2] data[3]
15: 1 3 3 -> data[1] data[3] data[3]
16: 2 2 2 -> data[2] data[2] data[2]
17: 2 2 3 -> data[2] data[2] data[3]
18: 2 3 3 -> data[2] data[3] data[3]
19: 3 3 3 -> data[3] data[3] data[3]

これは、要素の番号から求めるのは難しそうなので1つ前の要素から次の要素を求めるようにします。
1桁目に注目すると、2桁目か3桁目が変更されている所以外は、前の値+1されています。
そのため、2桁目、3桁目のカウントアップを検出すれば制御できそうです。
2桁目がカウントアップするところを抜き出すと、

0 0 3 -> 0 1 1
0 1 3 -> 0 2 2
0 2 3 -> 0 3 3

共通する事は、

  • 前の要素の1桁目が3
  • 2桁目が+1される
  • 1桁目と2桁目が同じになる

です。
同じように、3桁目がカウントアップするところを抜き出すと、

0 3 3 -> 1 1 1
1 3 3 -> 2 2 2
2 3 3 -> 3 3 3

共通する事は、

  • 前の要素の2桁目が3
  • 3桁目が+1される
  • 3桁目と2桁目と1桁目が同じになる

です。

これを関数に落とし込むと

  • 前の要素のi桁目にn-1が来る
  • i+1桁目を+1する
  • i+1桁以降をi+1桁と同じにする

とすればよいことになります。
ごちゃごちゃしたプログラムになってしまっていますが、以下のようになります。
ここでは、インデックスの組から値を求める関数getListElementsを定義して使っています。

def getListElements(lis, indices):
  """listからindicesで示される要素の組を返す"""
  return [lis[i] for i in indices]

import math

def combinationWithRepetition(n, r):
  return int(math.factorial(r + n - 1) / (math.factorial(r) * math.factorial(n - 1)))

def updateCombinationIndex(lastIndex, start, repetition=False):
  result = lastIndex[:start]
  x = lastIndex[start] + 1
  for i in range(start, len(lastIndex)):
    result.append(x)
    if(repetition == False):
      x += 1
  return result

def getComginationWithRepetitionIndex(length, r, lastIndex):
  result = []
  for i in range(r):
    if(len(lastIndex) == 0):
      result.append(0)
    elif(lastIndex[i] >= length - 1):
      result = updateCombinationIndex(lastIndex, i - 1, True)
      break
    elif(i == r - 1):
      result = updateCombinationIndex(lastIndex, i, True)
  return result

def combinationWithRepetitionList(data, r):
  length = len(data)
  total = combinationWithRepetition(length, r)
  result = []
  lastIndex = []
  for i in range(total):
    lastIndex = getComginationWithRepetitionIndex(length, r, lastIndex)
    result.append(getListElements(data, lastIndex))
  return result

ループ版 組み合わせ

n=4、r=3とすると、求めるべき組み合わせは、以下のようなものになります。

00: 0 1 2 -> data[0] data[1] data[2]
01: 0 1 3 -> data[0] data[1] data[3]
02: 0 2 3 -> data[0] data[2] data[3]
03: 1 2 3 -> data[1] data[2] data[3]

こちらも重複あり組み合わせと同じように求めてみます。
具体例が少なくて分かりづらいですが、2桁目がカウントアップする場所は、

  • 前の要素の1桁目が3
  • 2桁目が+1される
  • 1桁目が2桁目+1になる

3桁目がカウントアップする場所は、

  • 前の要素の2桁目が2
  • 3桁目が+1される
  • 2桁目が3桁目+1になる
  • 1桁目が2桁目+1になる

というようになっています。

  • 前の要素のi桁目にn-iが来る
  • i+1桁目を+1する
  • i+1-n桁目をi+1の要素+nにする

カウントアップする条件とその変更内容を変えれば、重複あり組み合わせと同じように作れます。
プログラムは、以下のようになります。

import math

def combination(n, r):
  if(n < r):
    return 0
  return int(math.factorial(n) / (math.factorial(r) * math.factorial(n - r)))

def getComginationIndex(length, r, lastIndex):
  result = []
  for i in range(r):
    if(len(lastIndex) == 0):
        result.append(i)
    elif(lastIndex[i] >= length - r + i):
      result = updateCombinationIndex(lastIndex, i - 1, False)
      break
    elif(i == r - 1):
      result = updateCombinationIndex(lastIndex, i, False)
  return result

def combinationList(data, r):
  length = len(data)
  total = combination(length, r)
  result = []
  lastIndex = []
  for i in range(total):
    lastIndex = getComginationIndex(length, r, lastIndex)
    result.append(getListElements(data, lastIndex))
  return result

ジェネレータ

せっかくPythonで作ったので、ジェネレータにもしてみます。
再帰版のジェネレータは、こう記述すれば動くと分かっているのですが何故そうしなければいけないのかが若干分かっていません。
また、再帰版ジェネレータでスタックが深い所で動作を停止させるとメモリなどに負荷がかかるのかもわかっていません。

再帰ジェネレータ版 重複あり順列

yieldのみで作成すると、以下のようになります。
rが0の時に値を返すために、yieldし、再帰関数自体がジェネラータを返すのでそれを回すためにfor文で回しています。
再帰関数に渡すdataもジェネレータにしてみようと思いましたが、今のところ難易度が高いので実現できませんでした。

def permutationWithRepetitionGeneratorRecursive(data, r):
  if r <= 0:
    return []

  return _permutationWithRepetitionGeneratorRecursive(data, r, [])

def _permutationWithRepetitionGeneratorRecursive(data, r, progress):
  if r == 0:
    yield progress
    return

  for i in range(len(data)):
    for j in _permutationWithRepetitionGeneratorRecursive(data, r - 1, progress + [data[i]]):
      yield j

yield fromを使うと以下のようになります。
yieldが2つ出てきてモヤモヤしていたのが無くなっりすっきりして良い感じです。

def _permutationWithRepetitionGeneratorRecursive(data, r, progress):
  if r == 0:
    yield progress
    return

  for i in range(len(data)):
    yield from _permutationWithRepetitionGeneratorRecursive(data, r - 1, progress + [data[i]])

再帰ジェネレータ版 順列

def permutationGeneratorRecursive(data, r):
  if r <= 0 or r > len(data):
    return []

  return _permutationGeneratorRecursive(data, r, [])

def _permutationGeneratorRecursive(data, r, progress):
  if r == 0:
    yield progress
    return

  for i in range(len(data)):
    yield from _permutationGeneratorRecursive(listExcludedIndices(data, [i]), r - 1, progress + [data[i]])

再帰ジェネレータ版 重複あり組み合わせ

def combinationWithRepetitionGeneratorRecursive(data, r):
  if r <= 0:
    return []

  return _combinationWithRepetitionGeneratorRecursive(data, r, 0, [])

def _combinationWithRepetitionGeneratorRecursive(data, r, start, progress):
  if r == 0:
    yield progress
    return

  for i in range(start, len(data)):
    yield from _combinationWithRepetitionGeneratorRecursive(data, r - 1, i, progress + [data[i]])

再帰ジェネレータ版 組み合わせ

def combinationGeneratorRecursive(data, r):
  if r == 0 or r > len(data):
    return []

  return _combinationGeneratorRecursive(data, r, 0, [])

def _combinationGeneratorRecursive(data, r, start, progress):
  if r == 0:
    yield progress
    return

  for i in range(start, len(data)):
    yield from _combinationGeneratorRecursive(data, r - 1, i + 1, progress + [data[i]])

ループジェネレータ版 重複あり順列

def permutationWithRepetitionGenerator(data, r):
  length = len(data)
  total = permutationWithRepetition(length, r)
  for i in range(total):
    element = []
    for digit in reversed(range(r)):
      element.append(data[int(i / pow(length, digit)) % length])
    yield element

ループジェネレータ版 順列

def permutationGenerator(data, r):
  length = len(data)
  total = permutation(length, r)
  for i in range(total):
    element = []
    copyData = data[:]
    for digit in range(r):
      l = len(copyData)
      countUp = total / functools.reduce(operator.mul, range(l, length + 1))
      index = int(i / countUp) % l
      element.append(copyData.pop(index))
    yield element

ループジェネレータ版 重複あり組み合わせ

def combinationWithRepetitionGenerator(data, r):
  length = len(data)
  total = combinationWithRepetition(length, r)
  lastIndex = []
  for i in range(total):
    lastIndex = getComginationWithRepetitionIndex(length, r, lastIndex)
    yield getListElements(data, lastIndex)

ループジェネレータ版 組み合わせ

def combinationGenerator(data, r):
  length = len(data)
  total = combination(length, r)
  lastIndex = []
  for i in range(total):
    lastIndex = getComginationIndex(length, r, lastIndex)
    yield getListElements(data, lastIndex)

最後に

言葉にしてみると難しいものです。
理論・解法を思いつてからプログラムにしたというより、プログラムから解法・理論を思いついている感じなのであんまり良い文章になりませんでした。
またところどころ説明が飛んでいるところもあります。
そういうところは自分の中で理解が足りなかったり、表現をどうしようか迷ったりした所です。

参考 Pythonドキュメントの例

def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

def combinations(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    for indices in permutations(range(n), r):
        if sorted(indices) == list(indices):
            yield tuple(pool[i] for i in indices)

def combinations_with_replacement(iterable, r):
    # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
    pool = tuple(iterable)
    n = len(pool)
    if not n and r:
        return
    indices = [0] * r
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != n - 1:
                break
        else:
            return
        indices[i:] = [indices[i] + 1] * (r - i)
        yield tuple(pool[i] for i in indices)

def combinations_with_replacement(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    for indices in product(range(n), repeat=r):
        if sorted(indices) == list(indices):
            yield tuple(pool[i] for i in indices)

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)

def product(*args, repeat=1):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)
92
81
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
92
81