사전에서 임의의 순서로 항목을 표시하는 방법 두 개의 인접 항목이 같은 항목이 아닌 방법

Question

우선 제목에 명시된 것보다 실제로 많은 제약이 있습니다. PLZ 읽기.

은 키가 항목으로 작동하는 dictionary<char,int>이며, 값은 출력에서 ​​발생 횟수를 의미합니다. (가중치가 있지만 교체가없는 것 같음) 예 : ('A', 2) ('B', 3) ('C', 1)

가능한 출력은 'babcab'

내가 그것을 구현하는 다음과 같은 방법으로 생각하고있을 것이다.

1. (누적 가중치, char)을 항목으로 포함하는 새 목록을 작성하십시오.
2. 무작위
3. 가 축적 된 가중치를 계산 목록에서 항목을 선택, 또한 0
4. 반복으로 무게 최근 그려 항목을 설정합니다.

'bacab'이 생성되었지만 더 이상 수행 할 수없는 상황이있을 수 있습니다 ('b'만 남았으나 즉각적인 반복이 허용되지 않으므로 가중치는 0으로 설정 됨). 이 경우 모든 결과가 삭제되고 처음부터 다시 시작됩니다.

다른 유용한 접근 방법이 있습니까?

또한 "해당 가중치를 0으로 설정"프로세스를 건너 뛰면 실행 불가능한 솔루션을 거부합니다. 예 : 벌써 나는 '밥'을 먹었다. 다음 rng 선택에서 'b'를 얻은 다음 'b'가 아닌 무언가를 얻을 때까지 무승부 과정을 다시 실행 한 다음 계속 진행합니다. 이것이 더 잘 수행됩니까?

Answer 1

이 재귀 알고리즘은 어떻습니까?

1. 모든 문자 목록 (후보 목록)을 무게에 따라 반복하여 작성하십시오. 선택한 항목 (문자) 다른 문자에 대한 스캔을 시작 한 후 솔루션 목록의 마지막 같은 경우
2. 는
3. 이 후보 목록
4. 에서 임의의 항목을 선택 (솔루션 목록) 문자의 빈 목록을 만듭니다 후보 목록에 (필요한 경우 주위에 배치).
5. 4 단계에서 해당 문자를 찾을 수없고 후보 목록이 비어 있지 않은 경우 역 추적
6. 선택한 문자를 솔루션 목록에 추가하십시오. 후보 목록은 솔루션 '철수'밖으로 빈 인쇄 인 경우
7. , 다른 3

내가 단계 아직 '철수'에 대한 아주 확실하지 않다 단계로 이동합니다,하지만 당신은 장군을 얻어야한다 생각.

Answer 2

이것을 시도해보십시오. 열거 형의 요소를 (의사) 임의 순서로 생성해야합니다.나는 목록에 사전에서 병합 권하고 싶습니다 : 의

AKA 사전 {B, 2}, {a는 3} {B} {B} {A} {A} {A}

된다

public static IEnumerable<T> RandomPermutation<T>(this IEnumerable<T> enumerable) 
    { 
     if (enumerable.Count() < 1) 
      throw new InvalidOperationException("Must have some elements yo"); 

     Random random = new Random(DateTime.Now.Millisecond); 
     while (enumerable.Any()) 
     { 
      int currentCount = enumerable.Count(); 
      int randomIndex = random.Next(0, currentCount); 
      yield return enumerable.ElementAt(randomIndex); 

      if (randomIndex == 0) 
       enumerable = enumerable.Skip(1); 
      else if (randomIndex + 1 == currentCount) 
       enumerable = enumerable.Take(currentCount - 1); 
      else 
      { 
       T removeditem = enumerable.ElementAt(randomIndex); 

       enumerable = enumerable.Where(item => !item.Equals(removeditem)); 
      } 
     } 
    } 

추가 순열이 필요한 경우 다른 무작위 순서로 다시 호출하기 만하면됩니다. 이 것은 모든 순열을 얻지는 못하지만 유용한 것을 찾아야합니다. 이것을베이스 라인으로 사용하여 솔루션을 얻을 수도 있습니다.

Answer 3

이것은 몇 가지 별도의 메소드로 분할되어야하며 일부 리팩터링을 사용할 수 있지만 올바른 결과가 나올 때까지 무작위로 물건을 움직이는 것에 의존하지 않는 방식으로 구현해야합니다. 를 문자열로

• 연결하여 모든 문자를 가지고 무작위 문자열을 통해 해당 문자열을

• 루프를 무작위 및 규칙을 위반하는 문자를 찾을 것입니다 얼마나 예측할 수없는 그런 식으로

• 문자열에서 해당 문자를 제거하십시오.
• 임의의 번호를 선택하십시오. 이 숫자를 "n 번째 유효한 위치에 제거 된 문자 넣기"로 사용하십시오.)
• 남은 문자열 주위를 돌면서 N 번째 유효한 위치를 찾아 문자를 다시 넣습니다.
• 더 이상의 위반까지 숯을 2 단계

• 반복 드롭 남아 유효한 위치

  시스템을 이용하여 발견되는 경우가있다; using System.Collections.Generic;

  네임 스페이스 { 클래스 프로그램 {

  static void Main(string[] args) 
      { 
       Random rnd = new Random(DateTime.Now.Millisecond); 
       Dictionary<char, int> chars = new Dictionary<char, int> { { 'a', 2 }, { 'b', 3 }, { 'c', 1 } }; 
  
       // Convert to a string with all chars 
       string basestring = ""; 
       foreach (var pair in chars) 
       { 
        basestring += new String(pair.Key, pair.Value); 
       } 
  
       // Randomize the string 
       string randomstring = ""; 
       while (basestring.Length > 0) 
       { 
        int randomIndex = rnd.Next(basestring.Length); 
        randomstring += basestring.Substring(randomIndex, 1); 
        basestring = basestring.Remove(randomIndex, 1); 
       } 
  
       // Now fix 'violations of the rule 
       // this can be optimized by not starting over each time but this is easier to read 
       bool done; 
       do 
       { 
        Console.WriteLine("Current string: " + randomstring); 
        done = true; 
        char lastchar = randomstring[0]; 
        for (int i = 1; i < randomstring.Length; i++) 
        {      
         if (randomstring[i] == lastchar) 
         { 
          // uhoh violation of the rule. We pick a random position to move it to 
          // this means it gets placed at the nth location where it doesn't violate the rule 
          Console.WriteLine("Violation at position {0} ({1})", i, randomstring[i]); 
  
          done = false; 
          char tomove = randomstring[i]; 
          randomstring = randomstring.Remove(i, 1); 
          int putinposition = rnd.Next(randomstring.Length); 
          Console.WriteLine("Moving to {0}th valid position", putinposition); 
  
          bool anyplacefound; 
          do 
          { 
           anyplacefound = false; 
           for (int replace = 0; replace < randomstring.Length; replace++) 
           { 
            if (replace == 0 || randomstring[replace - 1] != tomove) 
            { 
             // then no problem on the left side 
             if (randomstring[replace] != tomove) 
             { 
              // no problem right either. We can put it here 
              anyplacefound = true; 
              if (putinposition == 0) 
              { 
               randomstring = randomstring.Insert(replace, tomove.ToString()); 
               break; 
              } 
              putinposition--; 
             } 
            } 
           } 
          } while (putinposition > 0 && anyplacefound); 
  
          break; 
         } 
         lastchar = randomstring[i]; 
        } 
  
       } while (!done); 
  
       Console.WriteLine("Final string: " + randomstring); 
       Console.ReadKey(); 
      } 
  } 
  

  을} RandomString