Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
cache = {}
def join(a):
s = ""
for b in a:
s += str(b) + "_"
return s
def nCr(s1, r): # ただしmは、1 <= m <= len(s1) の範囲とする
a = s1[0] # 配列の最初の値を対象する
# a と組み合わせられる値は aを以外の配列を対象とすれば良い
s2 = s1[1:] # => [2, 3, 4, 5]
res = []
if r == 1: # 例外ケースとして処理
for a in s1:
res.append(a)
return res
elif r == 2:
for b in s2:
res.append([a, b])
else:
for bc in nCr(s2, r-1):
# bc.insert(0, a)
bc.append(a)
res.append(bc)
if len(s1) > r - 1:
prefix = join(s2)
key = "{prefix}{n}C{r}".format(prefix=prefix, n=len(s2), r=r)
if cache.get(key) is None:
cache[key] = nCr(s2, r)
return res + cache[key]
else:
return []
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.