Как перемешать цветные шарики? - PullRequest
Новая
       0

Как перемешать цветные шарики?

3 голосов
/ 21 октября 2011

У меня 400 шаров, из которых 100 - красные, 40 - желтые, 50 - зеленые, 60 - синие, 70 - фиолетовые, 80 - черные. (шарики одного цвета идентичны)

Мне нужен эффективный алгоритм перетасовки, чтобы после перетасовки шары были в списке, а

Любые 3 последовательных шара не одного цвета. например, я не могу иметь "красный, красный, красный, желтый ...."

И все перестановки "одинаково" могут произойти. (хорошо, если компромисс между эффективностью и беспристрастностью достаточно хорош, я не против большей эффективности, чем беспристрастность).

Я пытался приспособить Фишера-Йейтса-Кнута, но результат не идеален.

Почему Фишер-Йейтс недостаточно хорош? Как FY принимает обратное преобразование Монте-Карло. А выходной дистрибутив обрабатывает одни и те же цветные шары по-разному, т. Е. Генерирует смещенный результат для моих нужд.

И наивное мышление должно было бы отфильтровывать / возвращать обратно все плохие перестановки из всего пространства. Когда ограничение очень сильное, скажем, если у нас есть только 300 шаров, из которых 100 красных, то будет слишком много отслеживания / отказов назад, прежде чем получить соответствующую перестановку.

Так что, в конечном счете, я хотел бы иметь возможность перебирать все хорошие перестановки. Тем не менее, поскольку число допустимых перестановок слишком велико, я могу только случайным образом отобрать некоторые из них.

Ответы [ 2 ]

2 голосов
/ 21 октября 2011

Насколько я понимаю, алгоритм FYK меняет случайные позиции в массиве.Почему вы не можете просто воспроизвести цвета, как я описываю в псевдокоде? 

public IEnumerable<Color> GetColors()
{
   int count = 400;
   // queue or another data structure to hold the last generated colors
   Queue<Color> lastColors = new Queue<Color>(); 
   var availableColor = new Dictionary<Color, int> { 
     {Red, 100}, {Yellow, 40}, ...
   };
   Color nextColor = null;
   while(count > 0)
   {
     do {
       /* randomly pick from color buckets */
       nextColor = /* choose random color based on the weights*/;
     } while(/*it satisfies the condition, that it is not 3rd same color in a row*/)
     yield return nextColor;
     count--;
   }
}
1 голос
/ 21 октября 2011

Размышляя вслух, я бы попробовал

  • 'спроектировать' (придумать) (рекурсивный) генератор допустимых комбинаций;убедитесь, что он генерирует комбинации в детерминированном порядке;
  • преобразование генератора в детерминированную схему нумерации (магическое число, однозначно идентифицирующее любую из ваших допустимых комбинаций)в качестве аргумента, так что вам не нужно делать всю работу, чтобы добраться до 'n-й действительной комбинации' , но вместо этого вы можете "перейти" к нужной комбинации (для этого требуется ваше рекурсивное поколениефункция должна быть явной и детерминированной ; любой возврат может сделать это невозможным).

Теперь вы можете просто генерировать равномерно распределенное случайное «магическое» числомежду [0..max_number_of_valid_combination] 1 .Для каждого выбранного магического числа вы можете напечатать сгенерированную действительную комбинацию.

Если вам интересно, я мог бы найти время, чтобы попробовать себя в этом.(Я бы предпочел сделать это в C ++ / Python, но C # должен быть возможен (разве .Net 4.0 уже отправляет запрос BigInteger?))

1 (это может бытьогромное число, так что вы можете застрять в BigInteger и генерировать несколько случайных чисел для получения больших чисел. Убедитесь, что вы понимаете алгоритм распределения, чтобы гарантировать, что он действительно все еще равномерно распределен ...

2 существует значительный объем комбинаторики для получения правильных множителей для определения количества возможных «комбинаций хвостов» в конкретной точке во время генерации. Это узкое место сложности IMO

...