How to display the items from a dictionary in a random order but no two adjacent items being the same

First of all, there is actually more restrictions than stated in the title. Plz readon.

say, i have a dictionary<char,int> where key acts as the item, and value means the number of occurrence in the output. (somewhat like weighting but without replacement) e.g. ('a',2) ('b',3) ('c',1)

a possible output would be 'babcab'

I am thinking of th开发者_StackOverflowe following way to implement it.

1. build a new list containing (accumulated weightings,char) as its entry.
2. randomly select an item from the list,
3. recalculate the accumulated weightings, also set the recent drawn item weighing as 0.
4. repeat.

to some extent there might be a situation like such: 'bacab' is generated, but can do no further (as only 'b' left, but the weighting is set to 0 as no immediate repetition allowed). in this case i discard all the results and start over from the very beginning.

Is there any other good approach?

Also, what if i skip the "set the corresponding weighting to 0" process, instead I reject any infeasible solution. e.g. already i got 'bab'. In the next rng selection i get 'b', then i redo the draw process, until i get something that is not 'b', and then continue. Does this perform better?

How about this recursive algorithm.

1. Create a list of all characters (candidate list), repeating them according to their weight.
2. Create an empty list of characters (your solution list)
3. Pick a random entry from the candidate list
4. If the selected item (character) is the same as the last in solution list then start scanning for another character in the candidate list (wrapping around if needed).
5. If no such character in step 4 can be found and candidate list is not empty then backtrack
6. Append the selected character to the solution list.
7. If the candidate list is empty print out the solution and 'backtrack', else go to step 3.

I'm not quite sure about the 'backtrack' step yet, but you should get the general idea.

Try this out, it should generate a (pseudo) random ordering of the elements in your enumerable. I'd recommend flattening from your dictionary to a list:

AKA Dictionary of {b, 2}, {a, 3} becomes {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));
            }
        }
    }

If you need additional permutations, simply call it again for another random ordering. While this wont get you every permutation, you should find something useful. You can also use this as a base line to get a solution going.

This should be split into some seperate methods and could use some refactoring but the idea is to implement it in such a way that it does not depend on randomly moving things around till you get a valid result. That way you can't predict how long it would take

• Concatenate all chars to a string and randomize that string

• Loop through the randomized string and find any char that violates the rule

• Remove that char from the string
• Pick a random number. Use this number as "put the removed char at the nth valid position")
• Loop around the remaining string to find the Nth valid postion to put the char back.
• If there is no valid position left drop the char

• Repeat from step 2 until no more violations are found

  using System; using System.Collections.Generic;

  namespace RandomString { class Program {

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

  }