지능적으로 조합의 조합을 생성합니다

StackOverflow https://stackoverflow.com/questions/1622574

  •  06-07-2019
  •  | 
  •  

문제

내가 30 명의 학생들이 있고 5 명의 그룹으로 분할 될 수있는 모든 가능한 방법을 생성하고 싶다고 가정 해 봅시다 (주문은 관련이 없음).

한 그룹을 개별적으로 형성하기 위해 학생의 모든 조합을 찾는 방법을 알고 있습니다.http://www.merriampark.com/comb.htm). 해당 반복자와 일부 재귀를 사용하면 가능한 그룹 조합의 순열을 찾을 수 있습니다. 그러나 그룹이 선택된 순서는 관련이 없으며 실행 시간을 최소화하고 싶습니다. 그렇다면 가능한 그룹의 고유 한 조합을 어떻게 찾을 수 있습니까?

위의 알고리즘은 사전 조합을 생성하지 않기 위해 사전 순서를 사용합니다 ... 객체 대신 그룹에서 해당 아이디어를 사용할 수있는 방법이 있습니까?

나는 루비 잘 알고 자바/파이썬이 덜 잘 알고 있습니다. 조언에 미리 감사드립니다!

도움이 되었습니까?

해결책

글쎄, (30씨5*25씨5*20씨5*15씨5*10씨5*5씨5)/6! = 30!/(6!*5!6) = 123,378,675,083,039,376 30의 다른 파티톤은 5로 그룹으로 생성하므로 어떤 방법을 사용하든 모두 시간이 걸립니다.

그러나 일반적으로 그러한 파티션을 선택하는 좋은 방법은 요소에서 일부 순서를 사용하고 가장 높은 그룹화되지 않은 요소에 대한 그룹화를 찾은 다음 나머지 그룹을 그룹화하는 것입니다.

     find_partition = lambda do |elts|
        if elts.empty?
         [[]]
        else
         highest = elts.pop
         elts.combination(4).map do |others|
            find_partition[elts - others].map { |part| part << [highest,*others] }
         end.inject(:+)
        end
     end
     find_partition[(1..30).to_a]

이렇게하면 각 파티션 만 한 번만 생성합니다

다른 팁

이것은 오래된 질문이지만 어쨌든 기록을 위해서는 루비에서 내가하는 방법입니다.

class Array
  def groups_of_size(n)
    Enumerator.new do |yielder|
      if self.empty?
        yielder.yield([])
      else
        self.drop(1).combination(n-1).map { |vs| [self.first] + vs }.each do |values|
          (self - values).groups_of_size(n).each do |group|
            yielder.yield([values] + group)
          end   
        end
      end
    end
  end
end

출력이 매우 빠르게 증가 할 수 있기 때문에 열거자를 사용합니다. 엄격한 출력 (예 : 배열)은 유용하지 않습니다. 사용 예 :

>> pp [0, 1, 2, 3, 4, 5].groups_of_size(3).to_a
=> 
[[[0, 1, 2], [3, 4, 5]],
 [[0, 1, 3], [2, 4, 5]],
 [[0, 1, 4], [2, 3, 5]],
 [[0, 1, 5], [2, 3, 4]],
 [[0, 2, 3], [1, 4, 5]],
 [[0, 2, 4], [1, 3, 5]],
 [[0, 2, 5], [1, 3, 4]],
 [[0, 3, 4], [1, 2, 5]],
 [[0, 3, 5], [1, 2, 4]],
 [[0, 4, 5], [1, 2, 3]]]

순열에 대해 약간의 후 처리를 할 수 있습니다. 일부 의사 코드 (선택한 언어로 구현 ...) :

// We have a list of lists called 'permutations'
// combinations is an (empty) list of lists
for each permutation in permutations
{
   sortedPermutation = permutation.sort()
   if (! combinations.find(sortedPermutation) )
   {
       combinations.add(sortedPermutation);
   }
}

아마도 가장 효율적이지 않을 것입니다. 정렬을 추가하고 개인적으로 순열을 생성하는 코드와 비교합니다.

한 가지 가능성은 개별 그룹을 형성하기위한 모든 조합을 찾은 다음 해당 개별 그룹의 구성원을 포함하지 않는 조합을 생성하는 것입니다. 같은 것 :

List<List<Student>> combinations=Combinations(students);
public void GenerateCombinations(int startingIndex, List<List<Student>> currentGroups, int groupsLeft)
{
    if(groupsLeft==0) ProcessCombination(currentGroups);

    for(int i=startingIndex; i<combinations.Count; i++)
    {
        if combinations[i] does not contain a student in current groups
            GenerateCombinations(i+1, currentGroups + combinations[i], groupsLeft -1);
    }
}

그것에 대해 가장 효율적인 방법은 아니지만 그룹의 모든 조합을 생성해야합니다. 임시 조합 목록을 생성한다면 더 나은 성능을 발휘할 수 있다고 생각합니다. 모든 그룹에서 발생할 수없는 모든 그룹에서 제거되었지만 조금 더 복잡 할 것입니다.

약간 옆으로, 단일 그룹 5를 형성하려면 30 명의 학생으로 구성된 142,506 개의 조합이 있어야합니다.u003Csarcasm> 엄청난u003C/sarcasm> 수학 기술은 학생 그룹의 약 10^17 = 100 Quantrillion 조합이 있어야 함을 시사합니다 (30!/((5!^6)*6!); 30! 학생의 순서, 5 개 그룹의 주문은 중요하지 않습니다. , 그리고 그 6 개의 그룹의 주문은 중요하지 않습니다). 당신은 이것을 끝내기를 기다리는 잠시 거기에 앉아있을 것입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top