[TIL-20210721][アルゴリズム]Algorithmwith math

シーケンス/組合せ

シーケンスの組合せの問題の例

トランプをする

[A,B,C,D,E]カードは5枚ございますこの5枚のカードの中から3枚を選んでリストしたいです.次の条件を満たす場合を検索する必要があります.
条件3章を順番に選択します.
条件順序を考えずに選択する.
条件1を満たすすべての状況の数
1つ目の条件ですべての場合の数字を求めると、すべてのカードが1枚ずつリストされ、リストされたカードが3枚に達すると、リストカードが停止します.
条件を満たすには、次の方法で状況数を求めることができます.

の最初のカードを選択するには、次の5つの方法があります.
(A、B、C、D、Eの中から一つを選択します.)

1枚目の

カードをリストした後、2枚目のカードを選択する方法は4つあります.
(例えば、最初にAが選択された場合、残りのB、C、D、Eのうちの1つが選択される.)

2枚目の

カードをリストした後、3枚目のカードを選択する方法は3つあります.
(最初にAを引く、次にCを引くと、残りのB、D、Eのうちの1つを引く終了)

.
したがって、5 X 4 X 3=60の方法である.
n個のリストからその一部を選択してリストすることをシーケンスと呼ぶ.シーケンスは順番にリストする必要があります.例えば、3枚のカードを選択した場合、[A、B、D]と[A、D、B]のどちらもA、B、Dという同じカードを3枚選択したが、リストされた順番が異なるため、比較が必要となる.
シーケンスは一般化され,Permutationの略Pで表される.

条件2を満たすすべてのケース数
2つ目の場合,任意の数を求める場合には,3章を1つのグループとして選択しなければならない.2番目の条件を満たすには、次の方法で状況の数値を求めることができます.

シーケンスを検索します.

の順序で入手できる場合は、で繰り返しの場合をカウントします.

まず、組み合わせは順序と異なり、順序は考慮されません.状況の数を順番に計算すると,組合せとして正しくない.例えば、シーケンスでは、[A,B,C],[A,C,B],[B,C,A],[C,A,B],[C,B,A]の6つのケースがそれぞれ異なる場合と見なされるが、組み合わせでは、これら6つのケースがいずれも1つの場合と見なされる.言い換えれば、順番に選択すれば、繰り返しの場合は6倍になる.
ここに示す6つのケースの数は、3枚のカードの順番でリストされているすべてのケースの数です.3枚のカードをソート式に適用した結果は3!/(3-3)! = (3 X 2 X 1)/1=6.順序を考慮して、重複部分が現れるシーケンスのすべての可数を6つの重複項目で除算すると、組合せのすべての場合の可数が得られます.
したがって(5 X 4 X 3 X 2 X 1)/(3 X 2 X 1)X(2 X 1)=10となる.
組合せは一般化の過程を経て,組合せの略語Cとして表される.

5章で3章をランダムに選択した組み合わせで、すべての場合の数字=5 C 3=5!/(3! * 2!) = 10

一般式:nCr=n!/(r! * (n - r)!)

最大公倍数(GCD)/最小公倍数(LCM)

クリーンアップ用語

薬水:ある数を分ける

倍数:ある数の1,2,3...n倍数

公約数:2つ以上の公約数

公倍数:2つ以上の公倍数

最大公約数:2つ以上の公約数のうちの最大公約数

最小公倍数(LCM.Least Common Multiple):2つ以上の公倍数のうち最小公倍数

GCD/LCM式

最大公約数と最小公倍数をコードとして実現する方法はいくつかあるが,ユークリッドアーク除去法を用いてコードを式化することができる.

   function CGD (a, b) {
     if(a % b === 0) return b 
       
     return GCD(b, a % b) 
   }

   function LCM (a, b) {
     return a * b / GCD(a, b)
   }
     
// 위 코드를 삼항연산자를 사용해서 간단히 하면 아래와 같다.
   const GCD = (a, b) => a % b === 0 ? b : GCD(b, a % b);
   const LCM = (a, b) => a * b / GCD(a, b);

べき乗セット

集合{1,2,3}のすべてのサブセットは、{}、{1}、{2}、{3}、{1,2,3}、{1,3}および{1,2,3}としてリストされ、これらのサブセットの総数は8である.これらのすべての部分集合を総称してべき乗集合と呼ぶ.このような集合がある場合、その集合のすべての部分集合をべき乗セットと呼ぶ.すべての部分セットをリストする方法は、いくつかのステップに分けられます.部分集合をリストする方法では、先頭の要素(または任意の集合要素)が存在するかどうかに基づいて、ステップを分割する基準を決定します.

Step A:1以外の部分集合.
{3}のサブセットがリストされます(

Step B:2を除きます).
{}のサブセットがリストされます(

Step C:3を除きます).→ {}

Step C:{}のすべての部分セットには、{3}が追加されたセットがリストされます.→ {3}

Step B:{3}のすべての部分セットに{2}を追加したセットがリストされています.

Step C:{3}に追加されたすべての部分セットのセットをリストするには、{}のすべての部分セットに{2}を追加したセットをリストし、{}のすべての部分セットに{2,3}を追加したセットをリストします.→ {2}, {2, 3}

Step A:{2,3}のすべての部分セットに{1}が追加されたセットがリストされています.

Step B:{2,3}のすべての部分セットに{1}が追加されたセットがリストされ、{1}が{3}に追加されたすべての部分セットのセットがリストされます.

Step C:{3}に{1}を追加したすべての部分セットのセットをリストするには、{1}を{}に追加したすべての部分セットのセットをリストし、{1,3}を{}に追加したすべての部分セットをリストします.→ {1}, {1, 3}

Step C:{3}のすべての部分セットに{1,2}を追加したセットをリストするには、{}のすべての部分セットに{1,2}を追加したセットをリストし、{}のすべての部分セットに{1,2,3}を追加したセットをリストします.→ {1, 2}, {1, 2, 3}

2つのケース,すなわち元素が存在するか否かを考慮したので,集合中の元素がnの場合,全部分集合の個数は2 nである.たとえば、集合に4つの要素がある場合、すべての部分集合の個数は24であり、集合に5つの要素がある場合、25である.
べき乗セット構造例
べき乗セットを求める方法では、各ステップに注意して、ループ構造があることを確認します.ここで、ループ構造は、要素を排除することなく、集合を小さな単位に縮小する方法です.したがって、問題をより小さな範囲に縮小する再帰を適用できます.たとえば、関数を作成してべき乗セットの個数を返すと、べき乗セット関数は自分を呼び出し、問題をより小さな問題に縮小することで問題を解決します.問題を最小単位に縮小し、関数が返されるときにカウントを上げることでべき乗セットの個数を求めることができます.