n에서 k 요소의 모든 조합을 반환하는 알고리즘
https://stackoverflow.com/questions/127704
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
문자 배열을 인수로 사용하고 해당 문자 수를 선택하는 함수를 작성하고 싶습니다.
8개의 문자 배열을 제공하고 그 중에서 3개의 문자를 선택한다고 가정해 보겠습니다.그러면 다음을 얻을 수 있습니다:
8! / ((8 - 3)! * 3!) = 56
각각 3개의 문자로 구성된 배열(또는 단어)입니다.
해결책
컴퓨터 프로그래밍 아트 4 권 : Fascicle 3 내가 묘사하는 것보다 특정 상황에 더 잘 맞을 수있는 이들 톤이 있습니다.
회색 코드
당신이 겪게 될 문제는 물론 메모리와 매우 빨리 세트에 20 가지 요소로 문제가 생길 것입니다. 20씨3 = 1140. 세트를 반복하려면 수정 된 회색 코드 알고리즘을 사용하는 것이 가장 좋습니다. 이것들은 이전의 다음 조합을 생성하고 반복을 피합니다. 다른 용도로는이 중 많은 것이 있습니다. 연속 조합의 차이를 극대화하고 싶습니까? 최소화? 등등.
회색 코드를 설명하는 원래 논문 중 일부 :
주제를 다루는 다른 논문은 다음과 같습니다.
- Eades, Hickey의 효율적인 구현, 인접한 교환 조합 생성 알고리즘을 읽으십시오. (Pascal의 코드와 함께 PDF)
- 조합 생성기
- 조합 회색 코드 조사 (추신)
- 회색 코드에 대한 알고리즘
Chase 's twiddle (알고리즘)
필립 J 체이스,`알고리즘 382 : n 개체에서 m의 조합' (1970)
c.의 알고리즘...
사전 순서의 조합 색인 (버클 알고리즘 515)
지수 (사전 순서로)로 조합을 참조 할 수도 있습니다. 색인이 인덱스를 기준으로 오른쪽에서 왼쪽으로 어느 정도 변경되어야한다는 것을 인식하면 조합을 복구해야 할 것을 구성 할 수 있습니다.
그래서 우리는 {1,2,3,4,5,6} 세트를 가지고 있으며 세 가지 요소를 원합니다. {1,2,3} 우리는 요소의 차이가 하나이며 순서대로 최소라고 말할 수 있습니다. {1,2,4}는 하나의 변경 사항이 있으며 사전 어음 2입니다. 따라서 마지막 장소의 '변경'수는 사전 주문의 한 번의 변경 사항을 설명합니다. {1,3,4}의 하나의 변경 사항이있는 두 번째 장소에는 하나의 변경 사항이 있지만 2 위이기 때문에 더 많은 변경 사항을 설명합니다 (원래 세트의 요소 수에 비례).
내가 설명한 방법은 세트에서 인덱스에 이르기까지 해체입니다. 반대를 수행해야합니다. 이는 훨씬 까다 롭습니다. 이것이 방법입니다 버클 문제를 해결합니다. 나는 몇 가지 썼다 C를 계산합니다, 사소한 변경으로 - 세트를 나타내는 데 숫자 범위가 아닌 세트의 색인을 사용 했으므로 항상 0 ... n에서 작업하고 있습니다. 메모:
- 조합이 변하지 않기 때문에 {1,3,2} = {1,2,3} -우리는 사전 어류로 주문합니다.
- 이 방법에는 첫 번째 차이에 대한 세트를 시작하기위한 암시 적 0이 있습니다.
사전 순서의 조합 지수 (McCaffrey)
거기 있습니다 또 다른 방법:, 그 개념은 파악하고 프로그램하기 쉽지만 버클의 최적화가 없습니다. 다행히도 중복 조합을 생성하지 않습니다.
세트 
극대화됩니다 
, 어디 
.
예를 들어 : 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1). 따라서 네 가지의 27 번째 사전 사전 조합은 다음과 같습니다. {1,2,5,6}, 이는보고 싶은 세트의 색인입니다. 아래의 예 (OCAML), 필요합니다 choose 기능, 독자에게 왼쪽 :
(* this will find the [x] combination of a [set] list when taking [k] elements *)
let combination_maccaffery set k x =
(* maximize function -- maximize a that is aCb *)
(* return largest c where c < i and choose(c,i) <= z *)
let rec maximize a b x =
if (choose a b ) <= x then a else maximize (a-1) b x
in
let rec iterate n x i = match i with
| 0 -> []
| i ->
let max = maximize n i x in
max :: iterate n (x - (choose max i)) (i-1)
in
if x < 0 then failwith "errors" else
let idxs = iterate (List.length set) x k in
List.map (List.nth set) (List.sort (-) idxs)
작고 간단한 조합 반복자
다음 두 가지 알고리즘이 교훈적인 목적으로 제공됩니다. 그들은 반복자와 (보다 일반적인) 폴더 전체 조합을 구현합니다. 그것들은 가능한 한 빠르며 복잡성 O (N씨케이). 메모리 소비는 바로 묶여 있습니다 k.
우리는 반복자부터 시작하여 각 조합에 대해 사용자 제공 기능을 호출합니다.
let iter_combs n k f =
let rec iter v s j =
if j = k then f v
else for i = s to n - 1 do iter (i::v) (i+1) (j+1) done in
iter [] 0 0
보다 일반적인 버전은 초기 상태에서 시작하여 상태 변수와 함께 사용자 제공 기능을 호출합니다. 우리는 다른 상태 사이의 상태를 통과해야하기 때문에 우리는 for-loop를 사용하지 않고 대신 재귀를 사용하십시오.
let fold_combs n k f x =
let rec loop i s c x =
if i < n then
loop (i+1) s c @@
let c = i::c and s = s + 1 and i = i + 1 in
if s < k then loop i s c x else f c x
else x in
loop 0 0 [] x
다른 팁
C#:
public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
return k == 0 ? new[] { new T[0] } :
elements.SelectMany((e, i) =>
elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}
용법:
var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);
결과:
123
124
125
134
135
145
234
235
245
345
짧은 자바 솔루션 :
import java.util.Arrays;
public class Combination {
public static void main(String[] args){
String[] arr = {"A","B","C","D","E","F"};
combinations2(arr, 3, 0, new String[3]);
}
static void combinations2(String[] arr, int len, int startPosition, String[] result){
if (len == 0){
System.out.println(Arrays.toString(result));
return;
}
for (int i = startPosition; i <= arr.length-len; i++){
result[result.length - len] = arr[i];
combinations2(arr, len-1, i+1, result);
}
}
}
결과가 될 것입니다
[A, B, C]
[A, B, D]
[A, B, E]
[A, B, F]
[A, C, D]
[A, C, E]
[A, C, F]
[A, D, E]
[A, D, F]
[A, E, F]
[B, C, D]
[B, C, E]
[B, C, F]
[B, D, E]
[B, D, F]
[B, E, F]
[C, D, E]
[C, D, F]
[C, E, F]
[D, E, F]
이 문제에 대한 재귀 파이썬 솔루션을 제시 할 수 있습니까?
def choose_iter(elements, length):
for i in xrange(len(elements)):
if length == 1:
yield (elements[i],)
else:
for next in choose_iter(elements[i+1:len(elements)], length-1):
yield (elements[i],) + next
def choose(l, k):
return list(choose_iter(l, k))
예제 사용 :
>>> len(list(choose_iter("abcdefgh",3)))
56
나는 그것의 단순함을 좋아한다.
당신의 편지 배열이 다음과 같이 보인다 : "abcdefgh"라고 가정 해 봅시다. 현재 단어에 사용할 문자를 나타내는 세 가지 지수 (i, j, k)가 있습니다.
A B C D E F G H ^ ^ ^ i j k
먼저 K가 다양하므로 다음 단계는 다음과 같습니다.
A B C D E F G H ^ ^ ^ i j k
당신이 끝에 도달하면 당신은 계속해서 J와 K를 다시 다양하게합니다.
A B C D E F G H ^ ^ ^ i j k A B C D E F G H ^ ^ ^ i j k
당신이 j에 도달하면 g에 도달하기 시작합니다. i.
A B C D E F G H ^ ^ ^ i j k A B C D E F G H ^ ^ ^ i j k ...
코드로 작성된이 모습은 그런 것 같습니다
void print_combinations(const char *string)
{
int i, j, k;
int len = strlen(string);
for (i = 0; i < len - 2; i++)
{
for (j = i + 1; j < len - 1; j++)
{
for (k = j + 1; k < len; k++)
printf("%c%c%c\n", string[i], string[j], string[k]);
}
}
}
다음 재귀 알고리즘은 순서 세트에서 모든 k- 요소 조합을 선택합니다.
- 첫 번째 요소를 선택하십시오
i당신의 조합의 - 결합시키다
i각 조합과 함께k-1더 큰 요소 세트에서 재귀 적으로 선택된 요소i.
각각에 대해 위의 것을 반복하십시오 i 세트에서.
나머지 요소를보다 큰 것을 선택해야합니다. i, 반복을 피하기 위해. [3,5]는 [3]가 두 번 (조건이 [5] + [3]) 대신 [5]와 결합하여 한 번만 선택됩니다. 이 조건이 없으면 조합 대신 변형이 나타납니다.
이 스레드가 유용하고 Firebug에 팝업 할 수있는 JavaScript 솔루션을 추가 할 것이라고 생각했습니다. JS 엔진에 따라 시작 문자열이 커지면 약간의 시간이 걸릴 수 있습니다.
function string_recurse(active, rest) {
if (rest.length == 0) {
console.log(active);
} else {
string_recurse(active + rest.charAt(0), rest.substring(1, rest.length));
string_recurse(active, rest.substring(1, rest.length));
}
}
string_recurse("", "abc");
출력은 다음과 같습니다.
abc
ab
ac
a
bc
b
c
C ++에서 다음 루틴은 범위 [첫 번째, 마지막) 사이의 길이 거리 (첫 번째, k)의 모든 조합을 생성합니다.
#include <algorithm>
template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
/* Credits: Mark Nelson http://marknelson.us */
if ((first == last) || (first == k) || (last == k))
return false;
Iterator i1 = first;
Iterator i2 = last;
++i1;
if (last == i1)
return false;
i1 = last;
--i1;
i1 = k;
--i2;
while (first != i1)
{
if (*--i1 < *i2)
{
Iterator j = k;
while (!(*i1 < *j)) ++j;
std::iter_swap(i1,j);
++i1;
++j;
i2 = k;
std::rotate(i1,j,last);
while (last != j)
{
++j;
++i2;
}
std::rotate(k,i2,last);
return true;
}
}
std::rotate(first,k,last);
return false;
}
다음과 같이 사용할 수 있습니다.
#include <string>
#include <iostream>
int main()
{
std::string s = "12345";
std::size_t comb_size = 3;
do
{
std::cout << std::string(s.begin(), s.begin() + comb_size) << std::endl;
} while (next_combination(s.begin(), s.begin() + comb_size, s.end()));
return 0;
}
다음을 인쇄합니다.
123
124
125
134
135
145
234
235
245
345
static IEnumerable<string> Combinations(List<string> characters, int length)
{
for (int i = 0; i < characters.Count; i++)
{
// only want 1 character, just return this one
if (length == 1)
yield return characters[i];
// want more than one character, return this one plus all combinations one shorter
// only use characters after the current one for the rest of the combinations
else
foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))
yield return characters[i] + next;
}
}
파이썬의 짧은 예 :
def comb(sofar, rest, n):
if n == 0:
print sofar
else:
for i in range(len(rest)):
comb(sofar + rest[i], rest[i+1:], n-1)
>>> comb("", "abcde", 3)
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
설명을 위해, 재귀 방법은 다음 예제로 설명됩니다.
예 : ABCDE
3의 모든 조합은 다음과 같습니다.
- A 나머지에서 2의 모든 조합이있는 A (BCDE)
- b 나머지에서 2의 모든 조합이있는 b (cde)
- C 나머지에서 2의 모든 조합이있는 C (DE)
Haskell의 단순 재귀 알고리즘
import Data.List
combinations 0 lst = [[]]
combinations n lst = do
(x:xs) <- tails lst
rest <- combinations (n-1) xs
return $ x : rest
먼저 특별한 경우를 정의합니다.0개 요소를 선택합니다.이는 빈 목록인 단일 결과를 생성합니다(예:빈 목록을 포함하는 목록).
n > 0인 경우, x 목록의 모든 요소를 살펴보고 xs 다음의 모든 요소는 다음과 같습니다. x.
rest 추천 n - 1 요소 xs 재귀 호출을 사용하여 combinations.함수의 최종 결과는 각 요소가 포함된 목록입니다. x : rest (즉.다음을 포함하는 목록 x 머리로 그리고 rest 꼬리로) 모든 다른 값에 대해 x 그리고 rest.
> combinations 3 "abcde"
["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]
그리고 물론 Haskell은 게으르기 때문에 필요에 따라 목록이 점진적으로 생성되므로 기하급수적으로 큰 조합을 부분적으로 평가할 수 있습니다.
> let c = combinations 8 "abcdefghijklmnopqrstuvwxyz"
> take 10 c
["abcdefgh","abcdefgi","abcdefgj","abcdefgk","abcdefgl","abcdefgm","abcdefgn",
"abcdefgo","abcdefgp","abcdefgq"]
그리고 여기에는 많은 악의적 인 언어 인 Granddaddy Cobol이 있습니다.
각각 8 바이트의 34 개 요소 배열 (순수한 임의의 선택)을 가정 해 봅시다. 아이디어는 가능한 모든 4 요소 조합을 열거하고 배열에로드하는 것입니다.
우리는 4 개의 지수를 사용합니다.
배열은 다음과 같이 처리됩니다.
idx1 = 1
idx2 = 2
idx3 = 3
idx4 = 4
우리는 IDX4를 4에서 끝까지 다양하게합니다. 각 IDX4에 대해 4 개 그룹의 고유 한 조합을 얻습니다. IDX4가 배열 끝에 오면 IDX3을 1 씩 증가시키고 IDX4를 IDX3+1으로 설정합니다. 그런 다음 IDX4를 다시 끝까지 실행합니다. IDX1의 위치가 배열 끝에서 4 미만이 될 때까지 IDX3, IDX2 및 IDX1을 각각 증강시키는 이러한 방식으로 진행합니다. 알고리즘이 완료됩니다.
1 --- pos.1
2 --- pos 2
3 --- pos 3
4 --- pos 4
5
6
7
etc.
첫 번째 반복 :
1234
1235
1236
1237
1245
1246
1247
1256
1257
1267
etc.
COBOL 예 :
01 DATA_ARAY.
05 FILLER PIC X(8) VALUE "VALUE_01".
05 FILLER PIC X(8) VALUE "VALUE_02".
etc.
01 ARAY_DATA OCCURS 34.
05 ARAY_ITEM PIC X(8).
01 OUTPUT_ARAY OCCURS 50000 PIC X(32).
01 MAX_NUM PIC 99 COMP VALUE 34.
01 INDEXXES COMP.
05 IDX1 PIC 99.
05 IDX2 PIC 99.
05 IDX3 PIC 99.
05 IDX4 PIC 99.
05 OUT_IDX PIC 9(9).
01 WHERE_TO_STOP_SEARCH PIC 99 COMP.
* Stop the search when IDX1 is on the third last array element:
COMPUTE WHERE_TO_STOP_SEARCH = MAX_VALUE - 3
MOVE 1 TO IDX1
PERFORM UNTIL IDX1 > WHERE_TO_STOP_SEARCH
COMPUTE IDX2 = IDX1 + 1
PERFORM UNTIL IDX2 > MAX_NUM
COMPUTE IDX3 = IDX2 + 1
PERFORM UNTIL IDX3 > MAX_NUM
COMPUTE IDX4 = IDX3 + 1
PERFORM UNTIL IDX4 > MAX_NUM
ADD 1 TO OUT_IDX
STRING ARAY_ITEM(IDX1)
ARAY_ITEM(IDX2)
ARAY_ITEM(IDX3)
ARAY_ITEM(IDX4)
INTO OUTPUT_ARAY(OUT_IDX)
ADD 1 TO IDX4
END-PERFORM
ADD 1 TO IDX3
END-PERFORM
ADD 1 TO IDX2
END_PERFORM
ADD 1 TO IDX1
END-PERFORM.
다음은 Scala의 우아하고 일반적인 구현입니다. 99 스칼라 문제.
object P26 {
def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] =
ls match {
case Nil => Nil
case sublist@(_ :: tail) => f(sublist) ::: flatMapSublists(tail)(f)
}
def combinations[A](n: Int, ls: List[A]): List[List[A]] =
if (n == 0) List(Nil)
else flatMapSublists(ls) { sl =>
combinations(n - 1, sl.tail) map {sl.head :: _}
}
}
SQL 구문을 사용할 수있는 경우 LINQ를 사용하여 구조 또는 어레이의 필드에 액세스하거나 "알파벳"이라는 테이블이 하나만있는 "문자"라는 테이블이있는 데이터베이스에 직접 액세스 할 수 있다면 다음과 같은 적응할 수 있습니다. 암호:
SELECT A.Letter, B.Letter, C.Letter
FROM Alphabet AS A, Alphabet AS B, Alphabet AS C
WHERE A.Letter<>B.Letter AND A.Letter<>C.Letter AND B.Letter<>C.Letter
AND A.Letter<B.Letter AND B.Letter<C.Letter
이렇게하면 "알파벳"(3, 8, 10, 27 등이 될 수 있음)에 몇 글자가 몇 글자에도 불구하고 3 글자의 모든 조합을 반환합니다.
원하는 것이 조합보다는 모든 순열이라면 (즉, "ACB"및 "ABC"가 한 번만 나타나지 않고 다른 것으로 계산하기를 원합니다) 마지막 줄 (The and One)을 삭제하면 완료됩니다.
사후 편집 : 질문을 다시 읽은 후, 나는 필요한 것이 일반 알고리즘은 3 개 항목을 선택하는 경우에 특정한 알고리즘이 아닙니다. Adam Hughes의 답변은 완전한 답변입니다. 불행히도 나는 투표 할 수 없습니다 (아직). 이 답변은 간단하지만 정확히 3 개의 항목을 원할 때만 작동합니다.
조합 지수의 게으른 생성이있는 또 다른 C# 버전. 이 버전은 모든 값의 목록과 현재 조합의 값 사이의 매핑을 정의하기 위해 단일 지수를 유지합니다. 즉, 끊임없이 사용합니다. 확인) 전체 런타임 동안 추가 공간. 코드는 첫 번째 코드를 포함하여 개별 조합을 생성합니다. 확인) 시각.
public static IEnumerable<T[]> Combinations<T>(this T[] values, int k)
{
if (k < 0 || values.Length < k)
yield break; // invalid parameters, no combinations possible
// generate the initial combination indices
var combIndices = new int[k];
for (var i = 0; i < k; i++)
{
combIndices[i] = i;
}
while (true)
{
// return next combination
var combination = new T[k];
for (var i = 0; i < k; i++)
{
combination[i] = values[combIndices[i]];
}
yield return combination;
// find first index to update
var indexToUpdate = k - 1;
while (indexToUpdate >= 0 && combIndices[indexToUpdate] >= values.Length - k + indexToUpdate)
{
indexToUpdate--;
}
if (indexToUpdate < 0)
yield break; // done
// update combination indices
for (var combIndex = combIndices[indexToUpdate] + 1; indexToUpdate < k; indexToUpdate++, combIndex++)
{
combIndices[indexToUpdate] = combIndex;
}
}
}
테스트 코드 :
foreach (var combination in new[] {'a', 'b', 'c', 'd', 'e'}.Combinations(3))
{
System.Console.WriteLine(String.Join(" ", combination));
}
산출:
a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e
여기에는 C#에 코딩 된 해당 알고리즘의 게으른 평가 버전이 있습니다.
static bool nextCombination(int[] num, int n, int k)
{
bool finished, changed;
changed = finished = false;
if (k > 0)
{
for (int i = k - 1; !finished && !changed; i--)
{
if (num[i] < (n - 1) - (k - 1) + i)
{
num[i]++;
if (i < k - 1)
{
for (int j = i + 1; j < k; j++)
{
num[j] = num[j - 1] + 1;
}
}
changed = true;
}
finished = (i == 0);
}
}
return changed;
}
static IEnumerable Combinations<T>(IEnumerable<T> elements, int k)
{
T[] elem = elements.ToArray();
int size = elem.Length;
if (k <= size)
{
int[] numbers = new int[k];
for (int i = 0; i < k; i++)
{
numbers[i] = i;
}
do
{
yield return numbers.Select(n => elem[n]);
}
while (nextCombination(numbers, size, k));
}
}
그리고 테스트 부분 :
static void Main(string[] args)
{
int k = 3;
var t = new[] { "dog", "cat", "mouse", "zebra"};
foreach (IEnumerable<string> i in Combinations(t, k))
{
Console.WriteLine(string.Join(",", i));
}
}
도움이되기를 바랍니다!
Python에서 Project Euler에 사용한 순열 알고리즘이있었습니다.
def missing(miss,src):
"Returns the list of items in src not present in miss"
return [i for i in src if i not in miss]
def permutation_gen(n,l):
"Generates all the permutations of n items of the l list"
for i in l:
if n<=1: yield [i]
r = [i]
for j in permutation_gen(n-1,missing([i],l)): yield r+j
만약에
n<len(l)
반복없이 필요한 모든 조합이 있어야합니다. 필요합니까?
생성기이므로 다음과 같은 것으로 사용합니다.
for comb in permutation_gen(3,list("ABCDEFGH")):
print comb
https://gist.github.com/3118596
JavaScript에 대한 구현이 있습니다. K- 콤바인 화 및 모든 객체 배열의 모든 조합을 얻는 기능이 있습니다. 예 :
k_combinations([1,2,3], 2)
-> [[1,2], [1,3], [2,3]]
combinations([1,2,3])
-> [[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
Array.prototype.combs = function(num) {
var str = this,
length = str.length,
of = Math.pow(2, length) - 1,
out, combinations = [];
while(of) {
out = [];
for(var i = 0, y; i < length; i++) {
y = (1 << i);
if(y & of && (y !== of))
out.push(str[i]);
}
if (out.length >= num) {
combinations.push(out);
}
of--;
}
return combinations;
}
Clojure 버전 :
(defn comb [k l]
(if (= 1 k) (map vector l)
(apply concat
(map-indexed
#(map (fn [x] (conj x %2))
(comb (dec k) (drop (inc %1) l)))
l))))
당신의 편지 배열이 다음과 같이 보인다 : "abcdefgh"라고 가정 해 봅시다. 현재 단어에 사용할 문자를 나타내는 세 가지 지수 (i, j, k)가 있습니다.
A B C D E F G H ^ ^ ^ i j k
먼저 K가 다양하므로 다음 단계는 다음과 같습니다.
A B C D E F G H ^ ^ ^ i j k
당신이 끝에 도달하면 당신은 계속해서 J와 K를 다시 다양하게합니다.
A B C D E F G H ^ ^ ^ i j k A B C D E F G H ^ ^ ^ i j k
당신이 j에 도달하면 g에 도달하기 시작합니다. i.
A B C D E F G H ^ ^ ^ i j k A B C D E F G H ^ ^ ^ i j k ...
function initializePointers($cnt) {
$pointers = [];
for($i=0; $i<$cnt; $i++) {
$pointers[] = $i;
}
return $pointers;
}
function incrementPointers(&$pointers, &$arrLength) {
for($i=0; $i<count($pointers); $i++) {
$currentPointerIndex = count($pointers) - $i - 1;
$currentPointer = $pointers[$currentPointerIndex];
if($currentPointer < $arrLength - $i - 1) {
++$pointers[$currentPointerIndex];
for($j=1; ($currentPointerIndex+$j)<count($pointers); $j++) {
$pointers[$currentPointerIndex+$j] = $pointers[$currentPointerIndex]+$j;
}
return true;
}
}
return false;
}
function getDataByPointers(&$arr, &$pointers) {
$data = [];
for($i=0; $i<count($pointers); $i++) {
$data[] = $arr[$pointers[$i]];
}
return $data;
}
function getCombinations($arr, $cnt)
{
$len = count($arr);
$result = [];
$pointers = initializePointers($cnt);
do {
$result[] = getDataByPointers($arr, $pointers);
} while(incrementPointers($pointers, count($arr)));
return $result;
}
$result = getCombinations([0, 1, 2, 3, 4, 5], 3);
print_r($result);
기반 https://stackoverflow.com/a/127898/2628125, 그러나 어떤 크기의 포인터에 대해서는 더 추상적입니다.
이를 위해 SQL Server 2005에서 솔루션을 만들어 내 웹 사이트에 게시했습니다. http://www.jessemclain.com/downloads/code/sql/fn_getmchoosencombos.sql.htm
사용법을 보여주는 예는 다음과 같습니다.
SELECT * FROM dbo.fn_GetMChooseNCombos('ABCD', 2, '')
결과:
Word
----
AB
AC
AD
BC
BD
CD
(6 row(s) affected)
다음은 C ++의 제안입니다
이 솔루션이 전방 반복기를 가정하고 const_iterator가 될 수있는 반복기 유형에 제한이 적은 제한을 부과하려고 노력했습니다. 이것은 모든 표준 컨테이너와 함께 작동해야합니다. 인수가 의미가없는 경우 std :: invalid_argumnent를 던집니다.
#include <vector>
#include <stdexcept>
template <typename Fci> // Fci - forward const iterator
std::vector<std::vector<Fci> >
enumerate_combinations(Fci begin, Fci end, unsigned int combination_size)
{
if(begin == end && combination_size > 0u)
throw std::invalid_argument("empty set and positive combination size!");
std::vector<std::vector<Fci> > result; // empty set of combinations
if(combination_size == 0u) return result; // there is exactly one combination of
// size 0 - emty set
std::vector<Fci> current_combination;
current_combination.reserve(combination_size + 1u); // I reserve one aditional slot
// in my vector to store
// the end sentinel there.
// The code is cleaner thanks to that
for(unsigned int i = 0u; i < combination_size && begin != end; ++i, ++begin)
{
current_combination.push_back(begin); // Construction of the first combination
}
// Since I assume the itarators support only incrementing, I have to iterate over
// the set to get its size, which is expensive. Here I had to itrate anyway to
// produce the first cobination, so I use the loop to also check the size.
if(current_combination.size() < combination_size)
throw std::invalid_argument("combination size > set size!");
result.push_back(current_combination); // Store the first combination in the results set
current_combination.push_back(end); // Here I add mentioned earlier sentinel to
// simplyfy rest of the code. If I did it
// earlier, previous statement would get ugly.
while(true)
{
unsigned int i = combination_size;
Fci tmp; // Thanks to the sentinel I can find first
do // iterator to change, simply by scaning
{ // from right to left and looking for the
tmp = current_combination[--i]; // first "bubble". The fact, that it's
++tmp; // a forward iterator makes it ugly but I
} // can't help it.
while(i > 0u && tmp == current_combination[i + 1u]);
// Here is probably my most obfuscated expression.
// Loop above looks for a "bubble". If there is no "bubble", that means, that
// current_combination is the last combination, Expression in the if statement
// below evaluates to true and the function exits returning result.
// If the "bubble" is found however, the ststement below has a sideeffect of
// incrementing the first iterator to the left of the "bubble".
if(++current_combination[i] == current_combination[i + 1u])
return result;
// Rest of the code sets posiotons of the rest of the iterstors
// (if there are any), that are to the right of the incremented one,
// to form next combination
while(++i < combination_size)
{
current_combination[i] = current_combination[i - 1u];
++current_combination[i];
}
// Below is the ugly side of using the sentinel. Well it had to haave some
// disadvantage. Try without it.
result.push_back(std::vector<Fci>(current_combination.begin(),
current_combination.end() - 1));
}
}
여기에서 모든 말을하고 행한 O'Caml 코드가 온다. 알고리즘은 코드에서 분명합니다 ..
let combi n lst =
let rec comb l c =
if( List.length c = n) then [c] else
match l with
[] -> []
| (h::t) -> (combi t (h::c))@(combi t c)
in
combi lst []
;;
다음은 내가 최근에 Java로 쓴 코드입니다.이 코드는 "Outof"요소의 "Num"요소의 모든 조합을 계산하고 반환합니다.
// author: Sourabh Bhat (heySourabh@gmail.com)
public class Testing
{
public static void main(String[] args)
{
// Test case num = 5, outOf = 8.
int num = 5;
int outOf = 8;
int[][] combinations = getCombinations(num, outOf);
for (int i = 0; i < combinations.length; i++)
{
for (int j = 0; j < combinations[i].length; j++)
{
System.out.print(combinations[i][j] + " ");
}
System.out.println();
}
}
private static int[][] getCombinations(int num, int outOf)
{
int possibilities = get_nCr(outOf, num);
int[][] combinations = new int[possibilities][num];
int arrayPointer = 0;
int[] counter = new int[num];
for (int i = 0; i < num; i++)
{
counter[i] = i;
}
breakLoop: while (true)
{
// Initializing part
for (int i = 1; i < num; i++)
{
if (counter[i] >= outOf - (num - 1 - i))
counter[i] = counter[i - 1] + 1;
}
// Testing part
for (int i = 0; i < num; i++)
{
if (counter[i] < outOf)
{
continue;
} else
{
break breakLoop;
}
}
// Innermost part
combinations[arrayPointer] = counter.clone();
arrayPointer++;
// Incrementing part
counter[num - 1]++;
for (int i = num - 1; i >= 1; i--)
{
if (counter[i] >= outOf - (num - 1 - i))
counter[i - 1]++;
}
}
return combinations;
}
private static int get_nCr(int n, int r)
{
if(r > n)
{
throw new ArithmeticException("r is greater then n");
}
long numerator = 1;
long denominator = 1;
for (int i = n; i >= r + 1; i--)
{
numerator *= i;
}
for (int i = 2; i <= n - r; i++)
{
denominator *= i;
}
return (int) (numerator / denominator);
}
}
간결한 자바 스크립트 솔루션 :
Array.prototype.combine=function combine(k){
var toCombine=this;
var last;
function combi(n,comb){
var combs=[];
for ( var x=0,y=comb.length;x<y;x++){
for ( var l=0,m=toCombine.length;l<m;l++){
combs.push(comb[x]+toCombine[l]);
}
}
if (n<k-1){
n++;
combi(n,combs);
} else{last=combs;}
}
combi(1,toCombine);
return last;
}
// Example:
// var toCombine=['a','b','c'];
// var results=toCombine.combine(4);
다음은 임의의 길이 문자열에서 지정된 크기의 모든 조합을 제공하는 메소드입니다. Quinmars의 솔루션과 유사하지만 다양한 입력 및 k에서 작동합니다.
코드는 입력 'abcd'wk = 3에서 'dab'을 감싸도록 변경할 수 있습니다.
public void run(String data, int howMany){
choose(data, howMany, new StringBuffer(), 0);
}
//n choose k
private void choose(String data, int k, StringBuffer result, int startIndex){
if (result.length()==k){
System.out.println(result.toString());
return;
}
for (int i=startIndex; i<data.length(); i++){
result.append(data.charAt(i));
choose(data,k,result, i+1);
result.setLength(result.length()-1);
}
}
"ABCDE"의 출력 :
ABC ABD ABE ACD ACE ADE BCD BCE BCE BDE CDE
나는 이항 계수로 작업하기위한 일반적인 기능을 처리하기 위해 수업을 작성했습니다. 이는 문제가 발생하는 문제의 유형입니다. 다음과 같은 작업을 수행합니다.
모든 k-indexes를 모든 k-indexes를 좋은 형식으로 출력하여 모든 n을 파일에 선택합니다. K- 인덱스는보다 설명적인 문자열 또는 문자로 대체 될 수 있습니다. 이 방법은 이러한 유형의 문제를 매우 사소하게 만듭니다.
K- 인덱스를 분류 된 이항 계수 테이블에서 항목의 적절한 색인으로 변환합니다. 이 기술은 반복에 의존하는 구형 출판 기술보다 훨씬 빠릅니다. 파스칼의 삼각형에 내재 된 수학적 특성을 사용하여이를 수행합니다. 내 논문은 이것에 대해 이야기합니다. 나는이 기술을 처음 발견하고 출판 한 사람이라고 믿지만 틀릴 수 있습니다.
정렬 된 이항 계수 테이블에서 인덱스를 해당 K- 인덱스로 변환합니다.
용도 마크 도미너스 이항 계수를 계산하는 방법, 오버플로가 훨씬 적고 더 많은 숫자로 작동합니다.
이 클래스는 .NET C#로 작성되며 일반 목록을 사용하여 문제 (있는 경우)와 관련된 객체를 관리하는 방법을 제공합니다. 이 클래스의 생성자는 true가 관리 할 객체를 보유 할 일반 목록을 작성하는 inittable이라는 부울 값을 취합니다. 이 값이 False 인 경우 테이블을 생성하지 않습니다. 위의 4 가지 방법을 수행하기 위해 테이블을 만들 필요가 없습니다. 테이블에 액세스하기 위해 액세서 방법이 제공됩니다.
클래스를 사용하는 방법과 그 방법을 보여주는 관련 시험 클래스가 있습니다. 그것은 2 건으로 광범위하게 테스트되었으며 알려진 버그는 없습니다.
이 수업에 대해 읽고 코드를 다운로드하려면 이항 계수를 정제합니다.
이 클래스를 C ++로 변환하는 것은 어렵지 않아야합니다.
연산:
- 1에서 2^n까지 계산하십시오.
- 각 숫자를 이진 표현으로 변환하십시오.
- 위치에 따라 각 '비트'비트를 세트의 요소로 번역하십시오.
C#:
void Main()
{
var set = new [] {"A", "B", "C", "D" }; //, "E", "F", "G", "H", "I", "J" };
var kElement = 2;
for(var i = 1; i < Math.Pow(2, set.Length); i++) {
var result = Convert.ToString(i, 2).PadLeft(set.Length, '0');
var cnt = Regex.Matches(Regex.Escape(result), "1").Count;
if (cnt == kElement) {
for(int j = 0; j < set.Length; j++)
if ( Char.GetNumericValue(result[j]) == 1)
Console.Write(set[j]);
Console.WriteLine();
}
}
}
왜 작동합니까?
N- 요소 세트의 서브 세트와 N- 비트 서열 사이에 비록이 있습니다.
즉, 시퀀스를 계산하여 얼마나 많은 서브 세트가 있는지 알아낼 수 있습니다.
예를 들어, 아래에 세트 한 4 가지 요소는 {0,1} x {0, 1} x {0, 1} x {0, 1} (또는 2^4) 다른 시퀀스로 표시 될 수 있습니다.
그래서 - 우리가해야 할 일은 모든 조합을 찾기 위해 1에서 2^n까지 계산하는 것입니다. (우리는 빈 세트를 무시합니다.) 다음으로, 숫자를 이진 표현으로 번역하십시오. 그런 다음 세트의 요소를 'on'비트로 대체하십시오.
K 요소 결과 만 원한다면 K 비트가 'on'인 경우에만 인쇄하십시오.
(k 길이 서브 세트 대신 모든 서브 세트를 원한다면 CNT/kelement 부품을 제거하십시오.)
(증거는 컴퓨터 과학에 대한 MIT 무료 코스웨어 수학, Lehman et al, 섹션 11.2.2를 참조하십시오. https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/ )
악 대차를 뛰어 넘고 다른 솔루션을 게시합니다. 이것은 일반적인 Java 구현입니다. 입력: (int k) 선택해야 할 요소 수입니다 (List<T> list) 선택할 수있는 목록입니다. 조합 목록을 반환합니다 (List<List<T>>).
public static <T> List<List<T>> getCombinations(int k, List<T> list) {
List<List<T>> combinations = new ArrayList<List<T>>();
if (k == 0) {
combinations.add(new ArrayList<T>());
return combinations;
}
for (int i = 0; i < list.size(); i++) {
T element = list.get(i);
List<T> rest = getSublist(list, i+1);
for (List<T> previous : getCombinations(k-1, rest)) {
previous.add(element);
combinations.add(previous);
}
}
return combinations;
}
public static <T> List<T> getSublist(List<T> list, int i) {
List<T> sublist = new ArrayList<T>();
for (int j = i; j < list.size(); j++) {
sublist.add(list.get(j));
}
return sublist;
}
