[TIL] 131 [C#] 조합 모든 경우의 수 확인 재귀, IEnumerable yield return
카테고리: Til
조합 IEnumerable 재귀
조합 모든 경우의 수 재귀
조합의 모든 경우의 수 구하기
예시 1 재귀
로또 문제
n 개의 수 입력, 6개 숫자 조합.
재귀 조합 모든 경우의 수
/* 입력
7 1 2 3 4 5 6 7 처음 수(7) = 숫자의 개수 조합 할 숫자(1 2 3 4 5 6 7)
8 1 2 3 5 8 13 21 34 처음 수(8) = 숫자의 개수 조합 할 숫자(1 2 3 5 8 13 21 34)
0 종료
*/
class Program
{
static void Main()
{
{
var sw = new StreamWriter(Console.OpenStandardOutput());
while (true)
{
int[] nums = Array.ConvertAll(Console.ReadLine().Split(" "), Convert.ToInt32);
if (nums.Length==1)
{
break;
}
List<int> list = nums.Skip(1).ToList(); // 처음 수(숫자의 개수) 제외하고 list 생성
list.Sort();
List<int> sixnums = new List<int>(); // 조합 list
comb(list,6, sixnums,0); // (기존 리스트, 조합 할 수, 새로운 리스트, 시작인덱스)
sw.WriteLine();
}
sw.Flush(); sw.Close();
void comb(List<int> list, int k, List<int> current, int start)
{
if (current.Count == k)
{
sw.WriteLine(string.Join(" ", current));
return;
}
for (int i = start; i < list.Count; i++)
{
current.Add(list[i]); // 새로운 list 에 추가
comb(list, k, current, i+1); // 재귀
current.RemoveAt(current.Count-1); // if (current.Count == k) 로 return 된 후(6자리 채운 후)
// 마지막 숫자 지우고 i+1 숫자 넣기
// ex {1,2,3,4,5,*6*} -> {1,2,3,4,5} ->{1,2,3,4,5,7}-> if (current.Count == k) return ->
}
}
}
}
}
예시 2 IEnumerable yield return
IEnumerable
1. yield return이 실행될 때, 메서드는 현재 상태를 기억하고 다음 호출 시 해당 위치에서 다시 실행을 시작합니다.
2. 반복문 안에서 사용 시, 각 반복마다 중간 상태를 유지합니다.
3. 데이터의 각 요소를 순차적으로 반환
IEnumerable 조합 모든 경우의 수
var list = new List<int> { 1, 2, 3, 4 };
var combinations = GetCombinations(list, 3, 0); //1 2 3 4 에서 3자리 조합
foreach (var combination in combinations)
{
Console.WriteLine(string.Join(", ", combination));
}
// 제내릭<T>를 통해 어떤 List 든 반환 가능,
// 반환 값 : List<List<T>>
// List<T> = 각 조합
// List<List<T>> => 모든 조합을 담는 리스트
IEnumerable<List<T>> GetCombinations<T>(List<T> list, int k, int start)
{
if (k == 0) // 조합의 크기를 만족했을 때
{
yield return new List<T>(); // 빈 리스트 반환
yield break;
}
for (int i = start; i < list.Count; i++)
{
foreach (var combination in GetCombinations(list, k - 1, i + 1))
{
combination.Insert(0, list[i]); // 현재 요소 추가
yield return combination; // 조합 반환
}
}
}
실행 과정 1
1번째 start = 0 -> i = 0 일 때
// GetCombinations(list, 3, 0)
// start = 0, k = 3
for (int i = 0; i < list.Count; i++)
{
foreach (var combination in GetCombinations(list, 2, 1))
{
combination.Insert(0, list[i]); // 현재 요소 추가 list[i]=1
yield return combination; // 조합 반환 {1,2,3} {1,2,4} {1,3,4}
}
}
// GetCombinations(list, 2, 1)
// start = 1, k = 2
for (int i = 1; i < list.Count; i++)
{
foreach (var combination in GetCombinations(list, 1, 2))
{
combination.Insert(0, list[i]); // 현재 요소 추가 list[i]=2
yield return combination; // 조합 반환 {2,3},{2,4}
}
}
//i++
for (int i = 2; i < list.Count; i++)
{
foreach (var combination in GetCombinations(list, 1, 3))
{
combination.Insert(0, list[i]); // 현재 요소 추가 list[i]=3
yield return combination; // 조합 반환 {3,4}
}
}
//i++ i = 4>list.count 이면서 k!= 라서 X
// GetCombinations(list, 1, 2)
// start = 2, k = 1
for (int i = 2; i < list.Count; i++)
{
foreach (var combination in GetCombinations(list, 0, 3)) // if (k == 0) 새로운 리스트 생성
{
combination.Insert(0, list[i]); // 현재 요소 추가 list[i]=3
yield return combination; // 조합 반환 {3}
}
}
// i++
for (int i = 3; i < list.Count; i++)
{
foreach (var combination in GetCombinations(list, 0, 4)) // if (k == 0) 새로운 리스트 생성
{
combination.Insert(0, list[i]); // 현재 요소 추가 list[i]=4
yield return combination; // 조합 반환 {4}
}
}
// GetCombinations(list, 1, 3)
// start = 3, k = 1
for (int i = 3; i < list.Count; i++)
{
foreach (var combination in GetCombinations(list, 0, 4)) // if (k == 0) 새로운 리스트 생성
{
combination.Insert(0, list[i]); // 현재 요소 추가 list[i]=4
yield return combination; // 조합 반환 {4}
}
}
// k = 0 -> 새로운 리스트 반환
if (k == 0) // 조합의 크기를 만족했을 때
{
yield return new List<T>(); // 빈 리스트 반환
yield break;
}
실행 과정 2
2번째 start = 0 -> for 에서 i++로 i=1 일때
//GetCombinations(list, 3, 0)
//i++
//start 0, i=1
for (int i = 1; i < list.Count; i++)
{
foreach (var combination in GetCombinations(list, 2, 2))
{
combination.Insert(0, list[i]); // 현재 요소 추가 list[i]=2
yield return combination; // 조합 반환 {2,3,4}
}
}
//GetCombinations(list, 2, 2)
// start = 2, k = 2
for (int i = 2; i < list.Count; i++)
{
foreach (var combination in GetCombinations(list, 1, 3))// -> (list, 0, 4) 로{4}반환
{
combination.Insert(0, list[i]); // 현재 요소 추가 list[i]=3
yield return combination; // 조합 반환 {3,4}
}
}
// GetCombinations(list, 1, 3)
// start = 3, k = 1
for (int i = 3; i < list.Count; i++)
{
foreach (var combination in GetCombinations(list, 0, 4)) // if (k == 0) 새로운 리스트 생성
{
combination.Insert(0, list[i]); // 현재 요소 추가 list[i]=4
yield return combination; // 조합 반환 {4}
}
}
// k = 0 -> 새로운 리스트 반환
if (k == 0) // 조합의 크기를 만족했을 때
{
yield return new List<T>(); // 빈 리스트 반환
yield break;
}
조합의 개수 구하기
요소
n: 전체 요소
r: 선택할 요소
조합의 수 는 n! /r!(n-r)!
조합의 개수 코드
class Program
{
static void Main()
{
var list = new List<int> { 1, 2, 3, 4 };
Console.WriteLine(Combination(list.Count, 3)); // 4
}
static long Combination(int n, int r)
{
if (r > n) return 0; // 불가능한 경우
if (r == 0 || r == n) return 1;
return Factorial(n) / (Factorial(r) * Factorial(n - r));
}
static long Factorial(int num)
{
long result = 1;
for (int i = 2; i <= num; i++)
{
result *= i;
}
return result;
}
}
잡담, 일기?
조합 정리, IEnumerable에 대해 더 공부하기.
치킨 배달 문제
댓글남기기