Sequence
整列
複数の要素を繰り返しずに順番に抽出し、リストします.
順熱といいます.
nにおける任意の順序抽出r個の並列した個数
nPr = n×(n−1)×(n−2)×⋯⋯×(n−r+1) = n!/(n-r)!
A、B、Cの3文字は重複しない順序で、下図に示すように2文字のみリストされます.
3P2 = 3 * 2 = 6
2つの席があります.1つ目の席にはA、B、Cが3つ来られます.
2番目の位置では重複は許されませんので、1番目の位置の文字を除いて、他の2つがある可能性があります.
したがって3*2=6です.
すなわち
[A, B], [A, C], [B, A], [B, C], [C, A], [C, B]
Javaコードでこれを書きますimport java.util.Arrays;
import java.util.Scanner;
public class PermutationTest {
public static int N, R; // nPr 즉 n개의 원소중 r개를 중복 제거, 순서있게 나열하고 싶다.
public static char[] element, selected; // element는 n개의 원소를 담을 배열, selected는 n개의 원소중 r개를 선택한것을 담을 배열
public static boolean[] isSelected; // element의 각원소가 선택이 되었는지 알아보는 배열 선택이 되었으면 true 아니면 false
public static int totalcnt = 0; // 순열의 개수 3P2 = 6에서 6에 해당하는 값
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("nPr에서 n의 개수와 r의 개수가 될것을 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
N = sc.nextInt();
R = sc.nextInt();
element = new char[N];
selected = new char[R];
isSelected = new boolean[N];
System.out.print("nPr에서 n개의 원소를 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
for (int i = 0; i < N; i++) {
element[i] = sc.next().charAt(0);
}
Permutation(0);
System.out.println("순열의 총 가짓수 : " + totalcnt);
}
public static void Permutation(int cnt) {
if(cnt == R) {
System.out.println(Arrays.toString(selected));
totalcnt++;
return;
}
for (int i = 0; i < N; i++) {
if(isSelected[i] == true) continue;
selected[cnt] = element[i];
isSelected[i] = true;
Permutation(cnt + 1);
isSelected[i] = false;
}
}
}
Element配列は、A、B、Cを有するchar配列である.
isSelected配列は、要素配列と同じ長さのboolean配列である.
これはisSelected配列の各要素がtrueであるかfalseであるかに依存する.
要素配列の要素が選択されているかどうかです.
もちろん最初はAもBもCも選べなかったのでfalse.
一つ一つ選択するとtrueになります.
低コードから[A,A]を選択しなかった理由もif(isSelected[i] == true) continue;
上のコードのおかげです.
そして一番下.isSelected[i] = false;
このコードは、[A,B],[A,C]の出力後にBに切り替えたときに選択したAを消去するために使用されます.
だから[A,B],[A,C]を出力して、[B,A]を出力することができます.
そのコードがなければ[B,A]は出力されません.
繰り返し順
異なる要素には、繰り返しがあり、順番にいくつか抽出され、リストされます.
順熱といいます.
反復シーケンスと通常のシーケンスの最大の違いは、反復を許可することです.
nのr乗を表す.nΠr = n^r
A、B、Cの3文字は繰り返し順で、下図のように2文字だけ表示されます.
3^2 = 9
2つの席があります.1つ目の席にはA、B、Cが3つ来られます.
2番目の位置では繰り返しが許可されているので、1番目の位置の文字も来る可能性があります.
よって3*3=3^2=9です.
すなわち
[A, A], [A, B], [A, C], [B, A], [B, B], [B, C], [C, A], [C, B], [C, C]
Javaコードでこれを書きますimport java.util.Arrays;
import java.util.Scanner;
// 중복순열
public class PermutationWithRepetiton {
public static int N, R; // nΠr 즉 n개의 원소중 r개를 중복 있이, 순서있게 나열하고 싶다. n^r승
public static char[] element, selected; // element는 n개의 원소를 담을 배열, selected는 n개의 원소중 r개를 선택한것을 담을 배열
public static int totalcnt = 0; // 중복순열의 개수 3Π2 = 3^2 = 9 에서 9에 해당하는 값
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("nΠr에서 n의 개수와 r의 개수가 될것을 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
N = sc.nextInt();
R = sc.nextInt();
element = new char[N];
selected = new char[R];
System.out.print("nΠr에서 n개의 원소를 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
for (int i = 0; i < N; i++) {
element[i] = sc.next().charAt(0);
}
permutation_with_repetiton(0);
System.out.println("중복순열의 총 가짓수 : " + totalcnt);
}
public static void permutation_with_repetiton(int cnt) {
if(cnt == R) {
System.out.println(Arrays.toString(selected));
totalcnt++;
return;
}
for (int i = 0; i < N; i++) {
selected[cnt] = element[i];
permutation_with_repetiton(cnt + 1);
}
}
}
上記の一般的なシーケンスコードでは、
isSelected部分を消せばいいですとても簡単です.
繰り返しシーケンスは繰り返しを許可するため、要素全体でいずれかを選択して再選択することはできません.同じ悩みをする必要はないからだ.
コンポジット
異なる要素の中で繰り返しずにいくつかの組み合わせを順番に抽出することを組合せと呼ぶ.
n個ランダム抽出r個
nCr = nPr/r! = n!/(n-r)!r! (但しn>=r)
A,B,Cの3文字は,前後を問わず2文字のみ抽出し,下図に示す.
3C2 = 3P2/2! = 3
組み合わせて考えると便利です.
A、B、Cの3つの組み合わせから抽出した2つの組み合わせの数は
まず、3つのうちの2つを順番に並べた順番3 P 2を求める.
でもグループに順番がないのでそこに2が!どのくらい分けますか.
よって、3 P 2/2!=3つ3つです
すなわち
[A, B], [A, C], [B, C]
Javaコードでこれを書きます
キーは[A,B],[A,C],[B,C]
覚えておいてください.いつも右が左より大きいです.
A,B,Cの中から2つ選んだ問題のうち
入力配列がA,B,Cの順で受信されるとする.
ではAのindexは0,Bのindexは1,Cのindexは2である.
[A, B], [A, C], [B, C]
常に右要素のインデックスは左要素より大きい.
入力配列がC,A,Bの順で受信されるとする.
ではCのindexは0,Aのindexは1,Bのindexは2である.
[C, A], [C, B], [A, B]
常に右の要素は左の要素インデックスより大きい...
感じましたか…?
この感覚を表現してJavaでコードを書きます.import java.util.Arrays;
import java.util.Scanner;
public class CombinationTest {
public static int N, R; // nCr 즉 n개의 원소중 r개를 중복 없이, 순서없게 선택하고 싶다. nPr/r!
public static char[] element, selected; // element는 n개의 원소를 담을 배열, selected는 n개의 원소중 r개를 선택한것을 담을 배열
public static int totalcnt = 0; // 조합의 개수 3C2 = 3*2/2! = 3 에서 3에 해당하는 값
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("nCr에서 n의 개수와 r의 개수가 될것을 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
N = sc.nextInt();
R = sc.nextInt();
element = new char[N];
selected = new char[R];
System.out.print("nCr에서 n개의 원소를 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
for (int i = 0; i < N; i++) {
element[i] = sc.next().charAt(0);
}
combination(0, 0);
System.out.println("조합의 총 가짓수 : " + totalcnt);
}
public static void combination(int cnt, int start) {
if(cnt == R) {
System.out.println(Arrays.toString(selected));
totalcnt++;
return;
}
for (int i = start; i < N; i++) {
selected[cnt] = element[i];
combination(cnt + 1, i + 1);
}
}
}
常に右側の要素のインデックスが左の要素のインデックスより大きいように出力するには、次の手順に従います.
再帰のために変数(ここではstart)を別途設定する必要があります.
くりかえしくみたて
異なる要素では、順序にかかわらず、いくつかを抽出して組み合わせと呼ぶ.
nにおける任意の順序抽出r個の個数
nhr=r+(n-1)cr=n+r-1 cn-1(ただしn>=r)
A、B、Cの3文字を繰り返し、順番に関係なく2文字だけ抽出して下図のようにします.
重複コンビネーションは、通常のコンビネーションの重複を許容する場合です.
ポケットにA、B、C玉を3つ入れて、一度に2つ引くのが一般的です
缲り返し组み合わせは、ポケットにA、B、C玉を3つ入れて、まず1つ抜いてからポケットに入れます.そして選び直す.この場合、順序を考慮しないと、重複した組合せになります.△この順序を考えると、それは繰り返し順序です.
いずれにしても、上記の図では、A、B、Cの3つから2つ抽出した重複組合せの数は、式により
3+2-1 C 3-1=4 C 2=6,6種.
[A, A], [A, B], [A, C], [B, B], [B, C], [C, C]
このように表現することができます.
これをjavaコードに書きましょうimport java.util.Arrays;
import java.util.Scanner;
public class CombinationWithRepetiton {
public static int N, R; // nHr 즉 n개의 원소중 r개를 중복 있게, 순서없게 선택하고 싶다.
public static char[] element, selected; // element는 n개의 원소를 담을 배열, selected는 n개의 원소중 r개를 선택한것을 담을 배열
public static int totalcnt = 0; // 중복조합의 개수 3H2 = 3+2-1C3-1 = 4C2 = 6 에서 6에 해당하는 값
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("nHr에서 n의 개수와 r의 개수가 될것을 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
N = sc.nextInt();
R = sc.nextInt();
element = new char[N];
selected = new char[R];
System.out.print("nHr에서 n개의 원소를 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
for (int i = 0; i < N; i++) {
element[i] = sc.next().charAt(0);
}
combinationwithrepetiton(0, 0);
System.out.println("중복조합의 총 가짓수 : " + totalcnt);
}
public static void combinationwithrepetiton(int cnt, int start) {
if(cnt == R) {
System.out.println(Arrays.toString(selected));
totalcnt++;
return;
}
for (int i = start; i < N; i++) {
selected[cnt] = element[i];
combinationwithrepetiton(cnt + 1, i);
}
}
}
反復コンビネーションコードはコンビネーションコードとほぼ99.9%一致した.
唯一の違いは、繰り返しの組み合わせが繰り返しを許可することです.
最後の組み合わせwithrepetition(cnt+1,i);i+1の代わりにiを置換する.
ぶぶんしゅうごう
要素のセットのみからなるセット.
集合中の要素がn個ある場合,共通集合を含む部分集合の個数は2^n個である.
すなわち、すべての要素に適用される場合の数、すなわち、各要素が部分集合に含まれる場合、または部分集合に含まれない場合.
A、B、Cの3つの文字のサブセットを求めるのは以下の通りです.
前述したように、部分集合
いずれの場合も、各チャンバ内の要素は、1つの部分セットに含まれるか、または1つの部分セットに含まれない.
したがって,部分集合の総数は2^n個である.
だから上の写真の中にあります.
{A,B,C}, {A, B}, {A, C}, {A}, {B, C}, {B}, {C}, { }
全部で8つです.
これをjavaコードに書きましょうimport java.util.Scanner;
public class Subset {
public static int N; // N은 부분집합을 구하고 싶은 집합의 총 원소의 개수
public static char[] element;// element는 부분집합을 구하고 싶은 집합의 원소를 담을 배열
public static boolean[] isSelected; // element의 각 원소들이 선택되었는지 아닌지를 판단해주는 배열 (위 사진에서) true 이면 O, false이면 X
public static int totalcnt = 0; // 부분집합의 개수
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("(부부분집합을 구하고 싶은)집합의 총 원소의 개수를 입력해주세요(다 썼으면 엔터 눌러주세요) : ");
N = sc.nextInt();
element = new char[N];
isSelected = new boolean[N];
System.out.print("(부부분집합을 구하고 싶은)집합의 원소를 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
for (int i = 0; i < N; i++) {
element[i] = sc.next().charAt(0);
}
subset(0);
System.out.println("부분집합의 총 개수 : " + totalcnt);
}
public static void subset(int cnt) {
if(cnt == N) {
totalcnt++;
System.out.print("{");
for (int i = 0; i < N; i++) {
if(isSelected[i] == true)
System.out.print(element[i] + " ");
}
System.out.println("}");
return;
}
isSelected[cnt] = true;
subset(cnt+1);
isSelected[cnt] = false;
subset(cnt+1);
}
}
isSelected配列を分割します.
isSelected配列はtrueで選択され、falseは選択されていないことを示します.
cntが集合中の総要素の個数(部分集合を求めたい)に達すると、
復帰を停止する.
isSelected配列でtrueが選択されているため、同じインデックスの要素配列の要素
しゅつりょく
印刷しないでください.
一部の集合は主にリュックサックの問題に用いられる.Knapsackの問題は何ですか?
リュックサックの容量、すべてのものの重量と価格.
つまり、バックパックの容量を超えない場合、何を入れたら一番高くなるのかということです.
ただし、部分集合のコードは取得できます
必ずしも上記の方法で解く必要はありません.
例えばさっき述べたように.
集合{A,B,C}のサブセット{A,B,C},{A,C},{A,C},{B,C},{B,{C},{C},{C},{C},{C},{
は、3つの組み合わせ({A,B,C})+2つの組み合わせ({A,B},{A,C},{B,C})+1つの組み合わせ({A,{B,{C})+0つの組み合わせ({})です.
これは、上述した組合せコードを用いてコードを記述することもできる.
私はそのような方法でコードを書きます.import java.util.Arrays;
import java.util.Scanner;
public class Subset2 {
public static int N; // N은 부분집합을 구하고 싶은 집합의 총 원소의 개수
public static char[] element, selected;// element는 n개의 원소를 담을 배열
public static boolean[] isSelected;
public static int totalcnt = 0; // 부분집합의 개수
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("(부부분집합을 구하고 싶은)집합의 총 원소의 개수를 입력해주세요(다 썼으면 엔터 눌러주세요) : ");
N = sc.nextInt();
element = new char[N];
isSelected = new boolean[N];
System.out.print("(부부분집합을 구하고 싶은)집합의 원소를 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
for (int i = 0; i < N; i++) {
element[i] = sc.next().charAt(0);
}
for (int i = 0; i <= N; i++) {
selected = new char[i];
combination(0, 0, i);
}
System.out.println("부분집합의 총 개수 : " + totalcnt);
}
public static void combination(int cnt, int start, int R) {
if(cnt == R) {
totalcnt++;
System.out.println(Arrays.toString(selected));
return;
}
for (int i = start; i < N; i++) {
selected[cnt] = element[i];
combination(cnt+1, i+1, R);
}
}
}
上記の部分集合コードではncrに対応するrを0からnに増やし,各組合せを求めればよい.
Reference
この問題について(Sequence), 我々は、より多くの情報をここで見つけました
https://velog.io/@97ben/순열-조합-부분집합
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
import java.util.Arrays;
import java.util.Scanner;
public class PermutationTest {
public static int N, R; // nPr 즉 n개의 원소중 r개를 중복 제거, 순서있게 나열하고 싶다.
public static char[] element, selected; // element는 n개의 원소를 담을 배열, selected는 n개의 원소중 r개를 선택한것을 담을 배열
public static boolean[] isSelected; // element의 각원소가 선택이 되었는지 알아보는 배열 선택이 되었으면 true 아니면 false
public static int totalcnt = 0; // 순열의 개수 3P2 = 6에서 6에 해당하는 값
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("nPr에서 n의 개수와 r의 개수가 될것을 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
N = sc.nextInt();
R = sc.nextInt();
element = new char[N];
selected = new char[R];
isSelected = new boolean[N];
System.out.print("nPr에서 n개의 원소를 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
for (int i = 0; i < N; i++) {
element[i] = sc.next().charAt(0);
}
Permutation(0);
System.out.println("순열의 총 가짓수 : " + totalcnt);
}
public static void Permutation(int cnt) {
if(cnt == R) {
System.out.println(Arrays.toString(selected));
totalcnt++;
return;
}
for (int i = 0; i < N; i++) {
if(isSelected[i] == true) continue;
selected[cnt] = element[i];
isSelected[i] = true;
Permutation(cnt + 1);
isSelected[i] = false;
}
}
}
if(isSelected[i] == true) continue;
isSelected[i] = false;
異なる要素には、繰り返しがあり、順番にいくつか抽出され、リストされます.
順熱といいます.
反復シーケンスと通常のシーケンスの最大の違いは、反復を許可することです.
nのr乗を表す.nΠr = n^r
A、B、Cの3文字は繰り返し順で、下図のように2文字だけ表示されます.
3^2 = 9
2つの席があります.1つ目の席にはA、B、Cが3つ来られます.
2番目の位置では繰り返しが許可されているので、1番目の位置の文字も来る可能性があります.
よって3*3=3^2=9です.
すなわち
[A, A], [A, B], [A, C], [B, A], [B, B], [B, C], [C, A], [C, B], [C, C]
Javaコードでこれを書きます
import java.util.Arrays;
import java.util.Scanner;
// 중복순열
public class PermutationWithRepetiton {
public static int N, R; // nΠr 즉 n개의 원소중 r개를 중복 있이, 순서있게 나열하고 싶다. n^r승
public static char[] element, selected; // element는 n개의 원소를 담을 배열, selected는 n개의 원소중 r개를 선택한것을 담을 배열
public static int totalcnt = 0; // 중복순열의 개수 3Π2 = 3^2 = 9 에서 9에 해당하는 값
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("nΠr에서 n의 개수와 r의 개수가 될것을 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
N = sc.nextInt();
R = sc.nextInt();
element = new char[N];
selected = new char[R];
System.out.print("nΠr에서 n개의 원소를 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
for (int i = 0; i < N; i++) {
element[i] = sc.next().charAt(0);
}
permutation_with_repetiton(0);
System.out.println("중복순열의 총 가짓수 : " + totalcnt);
}
public static void permutation_with_repetiton(int cnt) {
if(cnt == R) {
System.out.println(Arrays.toString(selected));
totalcnt++;
return;
}
for (int i = 0; i < N; i++) {
selected[cnt] = element[i];
permutation_with_repetiton(cnt + 1);
}
}
}
上記の一般的なシーケンスコードでは、
isSelected部分を消せばいいですとても簡単です.
繰り返しシーケンスは繰り返しを許可するため、要素全体でいずれかを選択して再選択することはできません.同じ悩みをする必要はないからだ.
コンポジット
異なる要素の中で繰り返しずにいくつかの組み合わせを順番に抽出することを組合せと呼ぶ.
n個ランダム抽出r個
nCr = nPr/r! = n!/(n-r)!r! (但しn>=r)
A,B,Cの3文字は,前後を問わず2文字のみ抽出し,下図に示す.
3C2 = 3P2/2! = 3
組み合わせて考えると便利です.
A、B、Cの3つの組み合わせから抽出した2つの組み合わせの数は
まず、3つのうちの2つを順番に並べた順番3 P 2を求める.
でもグループに順番がないのでそこに2が!どのくらい分けますか.
よって、3 P 2/2!=3つ3つです
すなわち
[A, B], [A, C], [B, C]
Javaコードでこれを書きます
キーは[A,B],[A,C],[B,C]
覚えておいてください.いつも右が左より大きいです.
A,B,Cの中から2つ選んだ問題のうち
入力配列がA,B,Cの順で受信されるとする.
ではAのindexは0,Bのindexは1,Cのindexは2である.
[A, B], [A, C], [B, C]
常に右要素のインデックスは左要素より大きい.
入力配列がC,A,Bの順で受信されるとする.
ではCのindexは0,Aのindexは1,Bのindexは2である.
[C, A], [C, B], [A, B]
常に右の要素は左の要素インデックスより大きい...
感じましたか…?
この感覚を表現してJavaでコードを書きます.import java.util.Arrays;
import java.util.Scanner;
public class CombinationTest {
public static int N, R; // nCr 즉 n개의 원소중 r개를 중복 없이, 순서없게 선택하고 싶다. nPr/r!
public static char[] element, selected; // element는 n개의 원소를 담을 배열, selected는 n개의 원소중 r개를 선택한것을 담을 배열
public static int totalcnt = 0; // 조합의 개수 3C2 = 3*2/2! = 3 에서 3에 해당하는 값
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("nCr에서 n의 개수와 r의 개수가 될것을 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
N = sc.nextInt();
R = sc.nextInt();
element = new char[N];
selected = new char[R];
System.out.print("nCr에서 n개의 원소를 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
for (int i = 0; i < N; i++) {
element[i] = sc.next().charAt(0);
}
combination(0, 0);
System.out.println("조합의 총 가짓수 : " + totalcnt);
}
public static void combination(int cnt, int start) {
if(cnt == R) {
System.out.println(Arrays.toString(selected));
totalcnt++;
return;
}
for (int i = start; i < N; i++) {
selected[cnt] = element[i];
combination(cnt + 1, i + 1);
}
}
}
常に右側の要素のインデックスが左の要素のインデックスより大きいように出力するには、次の手順に従います.
再帰のために変数(ここではstart)を別途設定する必要があります.
くりかえしくみたて
異なる要素では、順序にかかわらず、いくつかを抽出して組み合わせと呼ぶ.
nにおける任意の順序抽出r個の個数
nhr=r+(n-1)cr=n+r-1 cn-1(ただしn>=r)
A、B、Cの3文字を繰り返し、順番に関係なく2文字だけ抽出して下図のようにします.
重複コンビネーションは、通常のコンビネーションの重複を許容する場合です.
ポケットにA、B、C玉を3つ入れて、一度に2つ引くのが一般的です
缲り返し组み合わせは、ポケットにA、B、C玉を3つ入れて、まず1つ抜いてからポケットに入れます.そして選び直す.この場合、順序を考慮しないと、重複した組合せになります.△この順序を考えると、それは繰り返し順序です.
いずれにしても、上記の図では、A、B、Cの3つから2つ抽出した重複組合せの数は、式により
3+2-1 C 3-1=4 C 2=6,6種.
[A, A], [A, B], [A, C], [B, B], [B, C], [C, C]
このように表現することができます.
これをjavaコードに書きましょうimport java.util.Arrays;
import java.util.Scanner;
public class CombinationWithRepetiton {
public static int N, R; // nHr 즉 n개의 원소중 r개를 중복 있게, 순서없게 선택하고 싶다.
public static char[] element, selected; // element는 n개의 원소를 담을 배열, selected는 n개의 원소중 r개를 선택한것을 담을 배열
public static int totalcnt = 0; // 중복조합의 개수 3H2 = 3+2-1C3-1 = 4C2 = 6 에서 6에 해당하는 값
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("nHr에서 n의 개수와 r의 개수가 될것을 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
N = sc.nextInt();
R = sc.nextInt();
element = new char[N];
selected = new char[R];
System.out.print("nHr에서 n개의 원소를 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
for (int i = 0; i < N; i++) {
element[i] = sc.next().charAt(0);
}
combinationwithrepetiton(0, 0);
System.out.println("중복조합의 총 가짓수 : " + totalcnt);
}
public static void combinationwithrepetiton(int cnt, int start) {
if(cnt == R) {
System.out.println(Arrays.toString(selected));
totalcnt++;
return;
}
for (int i = start; i < N; i++) {
selected[cnt] = element[i];
combinationwithrepetiton(cnt + 1, i);
}
}
}
反復コンビネーションコードはコンビネーションコードとほぼ99.9%一致した.
唯一の違いは、繰り返しの組み合わせが繰り返しを許可することです.
最後の組み合わせwithrepetition(cnt+1,i);i+1の代わりにiを置換する.
ぶぶんしゅうごう
要素のセットのみからなるセット.
集合中の要素がn個ある場合,共通集合を含む部分集合の個数は2^n個である.
すなわち、すべての要素に適用される場合の数、すなわち、各要素が部分集合に含まれる場合、または部分集合に含まれない場合.
A、B、Cの3つの文字のサブセットを求めるのは以下の通りです.
前述したように、部分集合
いずれの場合も、各チャンバ内の要素は、1つの部分セットに含まれるか、または1つの部分セットに含まれない.
したがって,部分集合の総数は2^n個である.
だから上の写真の中にあります.
{A,B,C}, {A, B}, {A, C}, {A}, {B, C}, {B}, {C}, { }
全部で8つです.
これをjavaコードに書きましょうimport java.util.Scanner;
public class Subset {
public static int N; // N은 부분집합을 구하고 싶은 집합의 총 원소의 개수
public static char[] element;// element는 부분집합을 구하고 싶은 집합의 원소를 담을 배열
public static boolean[] isSelected; // element의 각 원소들이 선택되었는지 아닌지를 판단해주는 배열 (위 사진에서) true 이면 O, false이면 X
public static int totalcnt = 0; // 부분집합의 개수
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("(부부분집합을 구하고 싶은)집합의 총 원소의 개수를 입력해주세요(다 썼으면 엔터 눌러주세요) : ");
N = sc.nextInt();
element = new char[N];
isSelected = new boolean[N];
System.out.print("(부부분집합을 구하고 싶은)집합의 원소를 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
for (int i = 0; i < N; i++) {
element[i] = sc.next().charAt(0);
}
subset(0);
System.out.println("부분집합의 총 개수 : " + totalcnt);
}
public static void subset(int cnt) {
if(cnt == N) {
totalcnt++;
System.out.print("{");
for (int i = 0; i < N; i++) {
if(isSelected[i] == true)
System.out.print(element[i] + " ");
}
System.out.println("}");
return;
}
isSelected[cnt] = true;
subset(cnt+1);
isSelected[cnt] = false;
subset(cnt+1);
}
}
isSelected配列を分割します.
isSelected配列はtrueで選択され、falseは選択されていないことを示します.
cntが集合中の総要素の個数(部分集合を求めたい)に達すると、
復帰を停止する.
isSelected配列でtrueが選択されているため、同じインデックスの要素配列の要素
しゅつりょく
印刷しないでください.
一部の集合は主にリュックサックの問題に用いられる.Knapsackの問題は何ですか?
リュックサックの容量、すべてのものの重量と価格.
つまり、バックパックの容量を超えない場合、何を入れたら一番高くなるのかということです.
ただし、部分集合のコードは取得できます
必ずしも上記の方法で解く必要はありません.
例えばさっき述べたように.
集合{A,B,C}のサブセット{A,B,C},{A,C},{A,C},{B,C},{B,{C},{C},{C},{C},{C},{
は、3つの組み合わせ({A,B,C})+2つの組み合わせ({A,B},{A,C},{B,C})+1つの組み合わせ({A,{B,{C})+0つの組み合わせ({})です.
これは、上述した組合せコードを用いてコードを記述することもできる.
私はそのような方法でコードを書きます.import java.util.Arrays;
import java.util.Scanner;
public class Subset2 {
public static int N; // N은 부분집합을 구하고 싶은 집합의 총 원소의 개수
public static char[] element, selected;// element는 n개의 원소를 담을 배열
public static boolean[] isSelected;
public static int totalcnt = 0; // 부분집합의 개수
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("(부부분집합을 구하고 싶은)집합의 총 원소의 개수를 입력해주세요(다 썼으면 엔터 눌러주세요) : ");
N = sc.nextInt();
element = new char[N];
isSelected = new boolean[N];
System.out.print("(부부분집합을 구하고 싶은)집합의 원소를 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
for (int i = 0; i < N; i++) {
element[i] = sc.next().charAt(0);
}
for (int i = 0; i <= N; i++) {
selected = new char[i];
combination(0, 0, i);
}
System.out.println("부분집합의 총 개수 : " + totalcnt);
}
public static void combination(int cnt, int start, int R) {
if(cnt == R) {
totalcnt++;
System.out.println(Arrays.toString(selected));
return;
}
for (int i = start; i < N; i++) {
selected[cnt] = element[i];
combination(cnt+1, i+1, R);
}
}
}
上記の部分集合コードではncrに対応するrを0からnに増やし,各組合せを求めればよい.
Reference
この問題について(Sequence), 我々は、より多くの情報をここで見つけました
https://velog.io/@97ben/순열-조합-부분집합
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
import java.util.Arrays;
import java.util.Scanner;
public class CombinationTest {
public static int N, R; // nCr 즉 n개의 원소중 r개를 중복 없이, 순서없게 선택하고 싶다. nPr/r!
public static char[] element, selected; // element는 n개의 원소를 담을 배열, selected는 n개의 원소중 r개를 선택한것을 담을 배열
public static int totalcnt = 0; // 조합의 개수 3C2 = 3*2/2! = 3 에서 3에 해당하는 값
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("nCr에서 n의 개수와 r의 개수가 될것을 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
N = sc.nextInt();
R = sc.nextInt();
element = new char[N];
selected = new char[R];
System.out.print("nCr에서 n개의 원소를 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
for (int i = 0; i < N; i++) {
element[i] = sc.next().charAt(0);
}
combination(0, 0);
System.out.println("조합의 총 가짓수 : " + totalcnt);
}
public static void combination(int cnt, int start) {
if(cnt == R) {
System.out.println(Arrays.toString(selected));
totalcnt++;
return;
}
for (int i = start; i < N; i++) {
selected[cnt] = element[i];
combination(cnt + 1, i + 1);
}
}
}
異なる要素では、順序にかかわらず、いくつかを抽出して組み合わせと呼ぶ.
nにおける任意の順序抽出r個の個数
nhr=r+(n-1)cr=n+r-1 cn-1(ただしn>=r)
A、B、Cの3文字を繰り返し、順番に関係なく2文字だけ抽出して下図のようにします.
重複コンビネーションは、通常のコンビネーションの重複を許容する場合です.
ポケットにA、B、C玉を3つ入れて、一度に2つ引くのが一般的です
缲り返し组み合わせは、ポケットにA、B、C玉を3つ入れて、まず1つ抜いてからポケットに入れます.そして選び直す.この場合、順序を考慮しないと、重複した組合せになります.△この順序を考えると、それは繰り返し順序です.
いずれにしても、上記の図では、A、B、Cの3つから2つ抽出した重複組合せの数は、式により
3+2-1 C 3-1=4 C 2=6,6種.
[A, A], [A, B], [A, C], [B, B], [B, C], [C, C]
このように表現することができます.
これをjavaコードに書きましょう
import java.util.Arrays;
import java.util.Scanner;
public class CombinationWithRepetiton {
public static int N, R; // nHr 즉 n개의 원소중 r개를 중복 있게, 순서없게 선택하고 싶다.
public static char[] element, selected; // element는 n개의 원소를 담을 배열, selected는 n개의 원소중 r개를 선택한것을 담을 배열
public static int totalcnt = 0; // 중복조합의 개수 3H2 = 3+2-1C3-1 = 4C2 = 6 에서 6에 해당하는 값
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("nHr에서 n의 개수와 r의 개수가 될것을 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
N = sc.nextInt();
R = sc.nextInt();
element = new char[N];
selected = new char[R];
System.out.print("nHr에서 n개의 원소를 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
for (int i = 0; i < N; i++) {
element[i] = sc.next().charAt(0);
}
combinationwithrepetiton(0, 0);
System.out.println("중복조합의 총 가짓수 : " + totalcnt);
}
public static void combinationwithrepetiton(int cnt, int start) {
if(cnt == R) {
System.out.println(Arrays.toString(selected));
totalcnt++;
return;
}
for (int i = start; i < N; i++) {
selected[cnt] = element[i];
combinationwithrepetiton(cnt + 1, i);
}
}
}
反復コンビネーションコードはコンビネーションコードとほぼ99.9%一致した.
唯一の違いは、繰り返しの組み合わせが繰り返しを許可することです.
最後の組み合わせwithrepetition(cnt+1,i);i+1の代わりにiを置換する.
ぶぶんしゅうごう
要素のセットのみからなるセット.
集合中の要素がn個ある場合,共通集合を含む部分集合の個数は2^n個である.
すなわち、すべての要素に適用される場合の数、すなわち、各要素が部分集合に含まれる場合、または部分集合に含まれない場合.
A、B、Cの3つの文字のサブセットを求めるのは以下の通りです.
前述したように、部分集合
いずれの場合も、各チャンバ内の要素は、1つの部分セットに含まれるか、または1つの部分セットに含まれない.
したがって,部分集合の総数は2^n個である.
だから上の写真の中にあります.
{A,B,C}, {A, B}, {A, C}, {A}, {B, C}, {B}, {C}, { }
全部で8つです.
これをjavaコードに書きましょうimport java.util.Scanner;
public class Subset {
public static int N; // N은 부분집합을 구하고 싶은 집합의 총 원소의 개수
public static char[] element;// element는 부분집합을 구하고 싶은 집합의 원소를 담을 배열
public static boolean[] isSelected; // element의 각 원소들이 선택되었는지 아닌지를 판단해주는 배열 (위 사진에서) true 이면 O, false이면 X
public static int totalcnt = 0; // 부분집합의 개수
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("(부부분집합을 구하고 싶은)집합의 총 원소의 개수를 입력해주세요(다 썼으면 엔터 눌러주세요) : ");
N = sc.nextInt();
element = new char[N];
isSelected = new boolean[N];
System.out.print("(부부분집합을 구하고 싶은)집합의 원소를 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
for (int i = 0; i < N; i++) {
element[i] = sc.next().charAt(0);
}
subset(0);
System.out.println("부분집합의 총 개수 : " + totalcnt);
}
public static void subset(int cnt) {
if(cnt == N) {
totalcnt++;
System.out.print("{");
for (int i = 0; i < N; i++) {
if(isSelected[i] == true)
System.out.print(element[i] + " ");
}
System.out.println("}");
return;
}
isSelected[cnt] = true;
subset(cnt+1);
isSelected[cnt] = false;
subset(cnt+1);
}
}
isSelected配列を分割します.
isSelected配列はtrueで選択され、falseは選択されていないことを示します.
cntが集合中の総要素の個数(部分集合を求めたい)に達すると、
復帰を停止する.
isSelected配列でtrueが選択されているため、同じインデックスの要素配列の要素
しゅつりょく
印刷しないでください.
一部の集合は主にリュックサックの問題に用いられる.Knapsackの問題は何ですか?
リュックサックの容量、すべてのものの重量と価格.
つまり、バックパックの容量を超えない場合、何を入れたら一番高くなるのかということです.
ただし、部分集合のコードは取得できます
必ずしも上記の方法で解く必要はありません.
例えばさっき述べたように.
集合{A,B,C}のサブセット{A,B,C},{A,C},{A,C},{B,C},{B,{C},{C},{C},{C},{C},{
は、3つの組み合わせ({A,B,C})+2つの組み合わせ({A,B},{A,C},{B,C})+1つの組み合わせ({A,{B,{C})+0つの組み合わせ({})です.
これは、上述した組合せコードを用いてコードを記述することもできる.
私はそのような方法でコードを書きます.import java.util.Arrays;
import java.util.Scanner;
public class Subset2 {
public static int N; // N은 부분집합을 구하고 싶은 집합의 총 원소의 개수
public static char[] element, selected;// element는 n개의 원소를 담을 배열
public static boolean[] isSelected;
public static int totalcnt = 0; // 부분집합의 개수
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("(부부분집합을 구하고 싶은)집합의 총 원소의 개수를 입력해주세요(다 썼으면 엔터 눌러주세요) : ");
N = sc.nextInt();
element = new char[N];
isSelected = new boolean[N];
System.out.print("(부부분집합을 구하고 싶은)집합의 원소를 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
for (int i = 0; i < N; i++) {
element[i] = sc.next().charAt(0);
}
for (int i = 0; i <= N; i++) {
selected = new char[i];
combination(0, 0, i);
}
System.out.println("부분집합의 총 개수 : " + totalcnt);
}
public static void combination(int cnt, int start, int R) {
if(cnt == R) {
totalcnt++;
System.out.println(Arrays.toString(selected));
return;
}
for (int i = start; i < N; i++) {
selected[cnt] = element[i];
combination(cnt+1, i+1, R);
}
}
}
上記の部分集合コードではncrに対応するrを0からnに増やし,各組合せを求めればよい.
Reference
この問題について(Sequence), 我々は、より多くの情報をここで見つけました
https://velog.io/@97ben/순열-조합-부분집합
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
import java.util.Scanner;
public class Subset {
public static int N; // N은 부분집합을 구하고 싶은 집합의 총 원소의 개수
public static char[] element;// element는 부분집합을 구하고 싶은 집합의 원소를 담을 배열
public static boolean[] isSelected; // element의 각 원소들이 선택되었는지 아닌지를 판단해주는 배열 (위 사진에서) true 이면 O, false이면 X
public static int totalcnt = 0; // 부분집합의 개수
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("(부부분집합을 구하고 싶은)집합의 총 원소의 개수를 입력해주세요(다 썼으면 엔터 눌러주세요) : ");
N = sc.nextInt();
element = new char[N];
isSelected = new boolean[N];
System.out.print("(부부분집합을 구하고 싶은)집합의 원소를 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
for (int i = 0; i < N; i++) {
element[i] = sc.next().charAt(0);
}
subset(0);
System.out.println("부분집합의 총 개수 : " + totalcnt);
}
public static void subset(int cnt) {
if(cnt == N) {
totalcnt++;
System.out.print("{");
for (int i = 0; i < N; i++) {
if(isSelected[i] == true)
System.out.print(element[i] + " ");
}
System.out.println("}");
return;
}
isSelected[cnt] = true;
subset(cnt+1);
isSelected[cnt] = false;
subset(cnt+1);
}
}
import java.util.Arrays;
import java.util.Scanner;
public class Subset2 {
public static int N; // N은 부분집합을 구하고 싶은 집합의 총 원소의 개수
public static char[] element, selected;// element는 n개의 원소를 담을 배열
public static boolean[] isSelected;
public static int totalcnt = 0; // 부분집합의 개수
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("(부부분집합을 구하고 싶은)집합의 총 원소의 개수를 입력해주세요(다 썼으면 엔터 눌러주세요) : ");
N = sc.nextInt();
element = new char[N];
isSelected = new boolean[N];
System.out.print("(부부분집합을 구하고 싶은)집합의 원소를 입력해주세요(한칸씩 띄어써서 다 썼으면 엔터 눌러주세요) : ");
for (int i = 0; i < N; i++) {
element[i] = sc.next().charAt(0);
}
for (int i = 0; i <= N; i++) {
selected = new char[i];
combination(0, 0, i);
}
System.out.println("부분집합의 총 개수 : " + totalcnt);
}
public static void combination(int cnt, int start, int R) {
if(cnt == R) {
totalcnt++;
System.out.println(Arrays.toString(selected));
return;
}
for (int i = start; i < N; i++) {
selected[cnt] = element[i];
combination(cnt+1, i+1, R);
}
}
}
Reference
この問題について(Sequence), 我々は、より多くの情報をここで見つけました https://velog.io/@97ben/순열-조합-부분집합テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol