n에서 k 요소의 모든 조합을 반환하는 알고리즘
문자 배열을 인수로 사용하고 선택할 문자 수를 사용하는 함수를 작성하고 싶습니다.
8 개의 문자 배열을 제공하고 그 중에서 3 개의 문자를 선택한다고 가정합니다. 그러면 다음을 얻을 수 있습니다.
8! / ((8 - 3)! * 3!) = 56
각각 3 개의 문자로 구성된 반환 배열 (또는 단어).
Art of Computer Programming Volume 4 : Fascicle 3 에는 내가 설명하는 것보다 귀하의 특정 상황에 더 잘 맞을 수있는 많은 것들이 있습니다.
그레이 코드
당연히 마주 치게 될 문제는 물론 기억이고 꽤 빨리 당신은 세트의 20 개 요소에 의해 문제가 생길 것입니다 -20 C 3 = 1140. 그리고 세트를 반복하고 싶다면 수정 된 회색을 사용하는 것이 가장 좋습니다. 코드 알고리즘을 사용하여 모든 것을 메모리에 저장하지 않습니다. 이것들은 이전에서 다음 조합을 생성하고 반복을 피합니다. 다른 용도로 많은 것들이 있습니다. 연속적인 조합 간의 차이를 최대화하고 싶습니까? 최소화? 등등.
회색 코드를 설명하는 일부 원본 문서 :
다음은 주제를 다루는 몇 가지 다른 문서입니다.
- Eades, Hickey, Read Adjacent Interchange Combination Generation Algorithm의 효율적인 구현 (PDF, 코드는 Pascal)
- 조합 생성기
- 조합 회색 코드 조사 (PostScript)
- 그레이 코드를위한 알고리즘
체이스 트위들 (알고리즘)
Phillip J Chase, `Algorithm 382 : Combinations of M out of N Objects '(1970)
C의 알고리즘 ...
사전 순서의 조합 색인 (버클 알고리즘 515)
색인으로 조합을 참조 할 수도 있습니다 (사전 순). 색인이 색인에 따라 오른쪽에서 왼쪽으로 어느 정도 변경되어야한다는 것을 인식하면 조합을 복구해야하는 무언가를 구성 할 수 있습니다.
그래서, 우리는 세트 {1,2,3,4,5,6} ...을 가지고 있고 세 가지 요소를 원합니다. {1,2,3}라고 가정 해 보겠습니다. 요소 간의 차이가 1이고 순서대로 최소라고 말할 수 있습니다. {1,2,4}에는 한 번의 변경이 있으며 사전 순으로 2 번입니다. 따라서 마지막 위치의 '변경'수는 사전 순에서 한 번의 변경을 설명합니다. 두 번째 위치, 한 번의 변경 {1,3,4}에는 한 번의 변경이 있지만 두 번째 위치에 있기 때문에 더 많은 변경을 설명합니다 (원래 집합의 요소 수에 비례 함).
제가 설명한 방법은 해체입니다. 세트에서 인덱스까지, 우리는 그 반대로해야합니다. 이는 훨씬 더 까다 롭습니다. 이것이 버클 이 문제를 해결하는 방법입니다. 나는 그것들을 계산하기 위해 약간의 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 C k ) 인 가능한 한 빠릅니다 . 메모리 소비는에 의해 제한됩니다 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 루프를 사용하지 않고 대신 재귀를 사용합니다.
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]
이 문제에 대한 재귀 Python 솔루션을 제시해도 될까요?
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)이 있습니다. 다음으로 시작합니다.
ABCDEFGH ^ ^ ^ ijk
먼저 k를 변경하므로 다음 단계는 다음과 같습니다.
ABCDEFGH ^ ^ ^ ijk
끝에 도달하면 계속해서 j와 k를 다시 변경합니다.
ABCDEFGH ^ ^ ^ ijk ABCDEFGH ^ ^ ^ ijk
j에 도달하면 i도 변화하기 시작합니다.
ABCDEFGH ^ ^ ^ ijk ABCDEFGH ^ ^ ^ ijk ...
코드로 작성하면 다음과 같이 보입니다.
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-1i
i세트의 각각 에 대해 위를 반복하십시오 .
i반복을 피하기 위해 나머지 요소를보다 큰 것으로 선택하는 것이 중요합니다 . 이렇게하면 [3,5]가 두 번이 아니라 [3]과 [5]가 결합 된 것처럼 한 번만 선택됩니다 (조건이 [5] + [3]를 제거함). 이 조건이 없으면 조합 대신 변형을 얻을 수 있습니다.
이 스레드가 유용하다는 것을 알았고 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 ++에서 다음 루틴은 [first, last) 범위 사이의 길이 거리 (first, 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;
}
}
Python의 간단한 예 :
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의 모든 조합은 다음과 같습니다.
- 나머지 2의 모든 조합이있는 A (BCDE)
- 나머지 2 개의 모든 조합이있는 B (CDE)
- 나머지 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"]
그리고 여기에 많이 악의적 인 언어 인 할아버지 COBOL이 있습니다.
각각 8 바이트의 34 개 요소 배열을 가정 해 보겠습니다 (순수한 선택). 아이디어는 가능한 모든 4 개 요소 조합을 열거하고 배열에로드하는 것입니다.
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.
다음은 99 Scala Problems 에 설명 된대로 Scala의 우아하고 일반적인 구현입니다 .
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를 사용하여 구조 또는 배열의 필드에 액세스하거나 "알파벳"이라는 테이블이있는 데이터베이스에 문자 필드 "Letter"가 하나만있는 데이터베이스에 직접 액세스하는 경우) 다음을 적용 할 수 있습니다. 암호:
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
이렇게하면 "Alphabet"테이블에있는 문자 수에 관계없이 3 개의 문자 조합이 모두 반환됩니다 (3, 8, 10, 27 등이 될 수 있음).
원하는 것이 조합이 아닌 모든 순열 인 경우 (즉, "ACB"와 "ABC"가 한 번만 표시되는 것이 아니라 다른 것으로 간주되기를 원함) 마지막 줄 (AND 하나)을 삭제하면 완료됩니다.
사후 편집 : 질문을 다시 읽은 후 필요한 것은 3 개 항목을 선택하는 경우에 대한 특정 알고리즘 이 아니라 일반적인 알고리즘 이라는 것을 깨달았습니다 . Adam Hughes의 대답은 완전한 것입니다. 안타깝게도 투표 할 수 없습니다 (아직). 이 답변은 간단하지만 정확히 3 개 항목을 원할 때만 작동합니다.
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]]
조합 인덱스의 지연 생성이있는 또 다른 C # 버전입니다. 이 버전은 모든 값 목록과 현재 조합 값 사이의 매핑을 정의하기 위해 단일 인덱스 배열을 유지합니다. 즉 , 전체 런타임 동안 O (k) 추가 공간을 지속적으로 사용 합니다. 코드는 O (k) 시간 에 첫 번째 조합을 포함하여 개별 조합을 생성 합니다.
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));
}
}
도움이 되었기를 바랍니다.
파이썬에서 프로젝트 오일러에 사용한 순열 알고리즘이 있습니다.
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
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)이 있습니다. 다음으로 시작합니다.
ABCDEFGH ^ ^ ^ ijk
먼저 k를 변경하므로 다음 단계는 다음과 같습니다.
ABCDEFGH ^ ^ ^ ijk
끝에 도달하면 계속해서 j와 k를 다시 변경합니다.
ABCDEFGH ^ ^ ^ ijk ABCDEFGH ^ ^ ^ ijk
j에 도달하면 i도 변화하기 시작합니다.
ABCDEFGH ^ ^ ^ ijk ABCDEFGH ^ ^ ^ ijk ...
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 기반 이지만 모든 크기의 포인터에 대해 좀 더 추상적입니다.
여기에서 말하고 수행 한 모든 것이 이에 대한 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 []
;;
이를 위해 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));
}
}
다음은 최근에 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 bde cde
연산:
- 1에서 2 ^ n까지 세십시오.
- 각 숫자를 이진 표현으로 변환합니다.
- 위치에 따라 각 'on'비트를 세트의 요소로 변환하십시오.
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- 비트 시퀀스의 하위 집합 사이에는 bijection이 있습니다.
즉, 시퀀스를 세어 하위 집합이 몇 개 있는지 알아낼 수 있습니다.
예를 들어 아래의 네 가지 요소 집합은 {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 / )
문제의 유형 인 이항 계수로 작업하기위한 공통 함수를 처리하는 클래스를 작성했습니다. 다음 작업을 수행합니다.
모든 K- 인덱스를 N이 파일에 K를 선택하는 데 적합한 형식으로 출력합니다. K- 색인은 더 설명적인 문자열이나 문자로 대체 할 수 있습니다. 이 방법은 이러한 유형의 문제를 매우 간단하게 해결합니다.
K- 인덱스를 정렬 된 이항 계수 테이블에있는 항목의 적절한 인덱스로 변환합니다. 이 기술은 반복에 의존하는 이전에 게시 된 기술보다 훨씬 빠릅니다. 파스칼의 삼각형에 내재 된 수학적 속성을 사용하여이를 수행합니다. 내 논문은 이에 대해 이야기합니다. 나는이 기술을 발견하고 출판 한 최초의 사람이라고 생각하지만 틀릴 수 있습니다.
정렬 된 이항 계수 테이블의 인덱스를 해당 K- 인덱스로 변환합니다.
Uses Mark Dominus method to calculate the binomial coefficient, which is much less likely to overflow and works with larger numbers.
The class is written in .NET C# and provides a way to manage the objects related to the problem (if any) by using a generic list. The constructor of this class takes a bool value called InitTable that when true will create a generic list to hold the objects to be managed. If this value is false, then it will not create the table. The table does not need to be created in order to perform the 4 above methods. Accessor methods are provided to access the table.
There is an associated test class which shows how to use the class and its methods. It has been extensively tested with 2 cases and there are no known bugs.
이 클래스에 대해 읽고 코드를 다운로드하려면 Tablizing The Binomial Coeffieicent를 참조하십시오 .
이 클래스를 C ++로 변환하는 것은 어렵지 않습니다.
JavaScript, 생성기 기반, 재귀 적 접근 방식 :
function *nCk(n,k){
for(var i=n-1;i>=k-1;--i)
if(k===1)
yield [i];
else
for(var temp of nCk(i,k-1)){
temp.unshift(i);
yield temp;
}
}
function test(){
try{
var n=parseInt(ninp.value);
var k=parseInt(kinp.value);
log.innerText="";
var stop=Date.now()+1000;
if(k>=1)
for(var res of nCk(n,k))
if(Date.now()<stop)
log.innerText+=JSON.stringify(res)+" ";
else{
log.innerText+="1 second passed, stopping here.";
break;
}
}catch(ex){}
}n:<input id="ninp" oninput="test()">
>= k:<input id="kinp" oninput="test()"> >= 1
<div id="log"></div>이런 식으로 (감소 i및 unshift()) 조합 내부의 조합 및 요소를 내림차순으로 생성하여 다소 눈을 즐겁게합니다.
테스트는 1 초 후에 중지되므로 이상한 숫자를 입력하는 것이 비교적 안전합니다.
참고 URL : https://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n
'programing tip' 카테고리의 다른 글
| Git 1.7+의 모든 원격 브랜치를 어떻게 나열합니까? (0) | 2020.10.04 |
|---|---|
| null vs. undefined 및 == 및 ===의 차이점에 대한 JavaScript 검사 (0) | 2020.10.04 |
| PostgreSQL 자동 증가 (0) | 2020.10.04 |
| Bash 스크립트에서 사용자에게 확인을 요청하는 방법은 무엇입니까? (0) | 2020.10.04 |
| JavaScript에서 정확히 두 개의 소수로 숫자 서식 지정 (0) | 2020.10.04 |