Pythonで順列と組合せ

リスト(配列)と抜き取り数を与えると、抜き取り数に応じた全てのリストのリストを返します。

順列

def junretsu(balls, nukitorisu):
  arrs = []
  len_balls = len(balls)
  if len_balls < nukitorisu:
    return
  elif nukitorisu == 1:
    for ball in balls:
      arrs.append([ball])
  else:
    for i in range(0, len_balls):
      parts = balls[:]
      parts.pop(i)
      results = junretsu(parts, nukitorisu - 1)
      for result in results:
        result.insert(0,balls[i])
        arrs.append(result)
  return arrs

組合せ

def kumiawase(balls, nukitorisu):
  arrs = []
  len_balls = len(balls)
  if len_balls < nukitorisu:
    return
  elif nukitorisu == 1:
    for ball in balls:
      arrs.append([ball])
  else:
    for i in range(0, len_balls - nukitorisu + 1):
      results = kumiawase(balls[i + 1:], nukitorisu - 1)
      for result in results:
        result.insert(0, balls[i])
        arrs.append(result)
  return arrs

使い方

balls = [1, 2, 3, 4]
arrs = junretsu(balls, 3)
print(arrs)

結果
[[1, 2, 3], [1, 2, 4], [1, 3, 2], [1, 3, 4], [1, 4, 2], [1, 4, 3], [2, 1, 3], [2, 1, 4], [2, 3, 1], [2, 3, 4], [2, 4, 1], [2, 4, 3], [3, 1, 2], [3, 1, 4], [3, 2, 1], [3, 2, 4], [3, 4, 1], [3, 4, 2], [4, 1, 2], [4, 1, 3], [4, 2, 1], [4, 2, 3], [4, 3, 1], [4, 3, 2]]

balls = [1, 2, 3, 4]
arrs = kumiawase(balls, 3)
print(arrs)

結果
[[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]

itertoolsを使う

Pythonにはitertoolsというモジュールがあります。これを使うと簡単に順列、組合せを扱えます。

import itertools
balls = [1, 2, 3, 4]
arrs = list(itertools.permutations(balls, 3))
print(arrs)
arrs = list(itertools.combinations(balls, 3))
print(arrs)

結果
[(1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 3, 4), (1, 4, 2), (1, 4, 3), (2, 1, 3), (2, 1, 4), (2, 3, 1), (2, 3, 4), (2, 4, 1), (2, 4, 3), (3, 1, 2), (3, 1, 4), (3, 2, 1), (3, 2, 4), (3, 4, 1), (3, 4, 2), (4, 1, 2), (4, 1, 3), (4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2)]
[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]

コメント

タイトルとURLをコピーしました