如何以随机顺序显示词典中的项目，但没有两个相邻项目相同

Question

首先，实际上存在比标题中所述更多的限制。普茨读后。

说，我有一个dictionary<char,int>其中键作为项目，值意味着输出中出现的次数。 （有点像加权但没有替换） 例如（ '一个'，2）（ 'B'，3）（ 'C'，1）

一个可能的输出是 'babcab'

我想到的实施了以下的方法。

1. 建立一个包含（累计权重，字符）作为其条目的新列表。
2. 随机从列表中选择一个项目，
3. 重新计算累积权重，还设置了最近绘制的项目重达0.1
4. 重复。

在某种程度上可能会出现类似这样的情况：'bacab'已生成，但不能进一步生效（因为只有'b'离开，但权重设置为0，因为不允许立即重复）。在这种情况下，我放弃了所有的结果，并从一开始就重新开始。

有没有其他的好方法？

另外，如果我跳过“设置相应的权重为0”的过程，而不是我拒绝任何不可行的解决方案。例如我已经有了'bab'。在下一个选择中，我得到'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;

  命名空间RandomString { 类节目 {

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

  }