順列、組み合わせ

数Aの確率と同じで、すべてを数え上げれば解ける。
数え上げの手段として順列、組み合わせがある。
だから、これらでコードをさらっと書けるようにすれば、ほとんどの問題は解けるはず。
その上で実行時間、スタックオーバーフローなどの問題が生じたら違うアルゴリズムを検討する。

### 組み合わせ
def comb(arr, n, idx = 0, acc = [])
  return [acc] if acc.length == n
  return [] if arr.length == idx

  ## idx番目より後ろの要素から選ぶ
  (idx...arr.length).reduce([]) do |acc2, i|
    acc2 + comb(arr, n, i+1, [*acc, arr[i]])
    # i番目も含むと重複組合せ
    # acc2 + comb(arr, n, i, [*acc, arr[i]]) 
  end
end

### 順列
def permu(arr, n, acc = [])
  return [acc] if acc.length == n

  ## すでに含まれてる要素を取り除く
  ## ここ消すと重複順列になる
  newArr = arr.select { |el| !acc.include?(el) }

  newArr.reduce([]) do |acc2, el|
    acc2 + permu(newArr, n, [*acc, el])
  end
end

#その他
### 組み合わせ
### 考え方：idx番目の要素を追加するかで分ける
def combV2(arr, n, idx = 0, acc = [])
  return [acc] if acc.length == n
  return [] if idx == arr.length

  combV2(arr, n, idx + 1, [*acc, arr[idx]]) + combV2(arr, n, idx + 1, [*acc])
end

引数にnを使ってるけどrにすべきだった

追記

def rec(n,i,S)
return if i == n
S[i]=0
rec(n,i+1,S)
S[i]=1
rec(n,i+1,S)
end
#選ぶか選ばないかの01でつくる

参考
qiita.com