ランダムな順序で辞書から項目を表示する方法隣接する2つの項目が同じではない

Question

まず、実際にタイトルに記載されている制限よりも多くの制限があります。 Plz readon。

たとえば、私はdictionary<char,int>を持っています。ここでkeyはアイテムとして機能し、valueは出力の出現回数を意味します。 （重み付けに若干似ていますが、置換えなし） （ 'A'、2）（ 'B'、3）（ 'C'、1）

可能な出力は、私はそれを実装するには、次の方法を考えています 'babcab'

だろう。

1. （累積weightings、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}、{、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)); 
      } 
     } 
    } 

追加の並べ替えが必要な場合は、もう1つのランダムな並べ替えのためにもう一度呼び出すだけです。これはあなたにあらゆる順列を手に入れませんが、何か役に立つものを見つけなければなりません。これをベースラインとして使用して、解決策を得ることもできます。

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(); 
      } 
  } 
  

  }