배열을 다루는 중이며 배열 배열을 다루는 지 여부를 계산하기 위해 특정 매개 변수가있는 집합 생성에 대한 지침이 필요합니다.조합/순열 생성 (v 기호에 t- 세트)
두 입력을 받아서 - t과 v을 정수로 사용했습니다. v에는 배열의 고유 한 기호 (정수) 수가 포함됩니다. 이것은 모든 정수의 집합으로 가정 할 수 있습니다. 정수 t은이 집합에서 가져올 기호의 길이를 나타냅니다.
예를 들어 {0,1,2}의 경우 v = 3을 기호로 사용하고 t = 2이라고 가정합니다. 그런 다음 { (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), ..., (2,2) } 조합을 생성합니다. 일반적으로 나는 v^t 개의 조합을 생성 할 것입니다. 내가 사용하고있는 알고리즘보다 더 나은 알고리즘이 있는지 궁금하다. 아마도 아마도 덜 비싸다.
기본적으로 내가하고있는 일은 다른 기반을 세우는 것입니다. 예를 들어 위의 예에서 처음에는 배열에 t 공백이 0부터 할당됩니다. 각 패스에서 최하위 비트를 증가시키고이를 조합 또는 다른 데이터 구조로 변환하여 조합을 유지합니다. 최하위 비트가 오버플로되면이를 0으로 설정하고 다음 중요 비트를 증가시킵니다. 그것은 모두 다른 기반에서 세고 있습니다. 그래서 t=2 및 v=3에 대한 다음과 같은 출력으로 끝낼 것 :
00
01
02
10
11
12
20
21
22
나의 가장 큰 질문은 이것이다 -이 순열 또는 조합 문제? 저는 두 사람 사이의 세부 사항에 대해서는 조금 퍼지기 마련입니다. 나는 그것이 반복이 일어나기 때문에 순열이라고 믿는다. 질서가 중요하지 않기 때문이다.
마찬가지로이 알고리즘은 (잠재적으로) 큰 v을 처리하기에 충분합니까? t은 2 또는 3이되지만 v은 알 수없는 매개 변수가 제공됩니다. 길이 계산을위한 잘 알려진 알고리즘이 있습니까 tv 심볼을 설정합니까? 참고로 C++을 사용하고 있습니다.
캐리를 전파하는 시간 중 더 적은 비율을 소비하기 때문에 'v'가 증가함에 따라 계산 상각 된 비용이 ** 많이 내립니다 **. –
@ bgoers : 귀하의 예에서는 {01}과 {10}이 다르므로 조합의 유일한 문제는 아닙니다. 조합의 가능한 순열입니다. –
@OliCharlesworth 입력 해 주셔서 감사합니다. 그래서 v <= 500이라고 가정하면 (이 경우 제약 조건 때문에 안전하게 사용할 수 있습니다), 이것이 괜찮을 것이라고 생각하십니까? 그 시점에서 나는 그것이 공간의 복잡성에 대한 더 많은 질문이라고 추측하고있다. 그러나 이것은 너무 커다란 클러스터에서 돌아가고있다. 그래서 나는 너무 심하게 걱정하지 않는다. – bgoers