Перемешать список с некоторыми условиями

Question

У меня есть список элементов, которые можно легко сравнить с помощью Equals().Я должен перетасовать список, но перемешивание должно удовлетворять одному условию:

i-й элемент shuffledList[i] не должен совпадать ни с элементами на i +/- 1, ни с элементами на i +/- 2.Список следует считать круговым;то есть, за последним элементом в списке следует первый, и наоборот.

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

Примечание:

Я использую c # 4.0.

РЕДАКТИРОВАТЬ:

На основе некоторых ответов, я объясню немного больше:

• В списке не будет более 200 элементов, поэтому нет реальной необходимости в хорошей производительности.Если его вычисление занимает 2 секунды, это не лучшая вещь, но и это не конец света.Перемешанный список будет сохранен, и если реальный список не изменится, будет использован перетасованный список.

• Да, это «контролируемая» случайность, но я ожидаю, что на этом работают несколькометод будет возвращать разные перемешанные списки.

• Я внесу дополнительные изменения после того, как попробую некоторые из ответов ниже.

РЕДАКТИРОВАТЬ 2:

• Два примера списка, которые не работают с реализацией Sehe (у обоих есть решения):

Sample1:

`List<int> list1 = new List<int>{0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,6,6,6,7,7,7,7,8,8,8,8,9,9,9,9,9,10};`

Возможное решение:

List<int> shuffledList1 = new List<int> {9,3,1,4,7,9,2,6,8,1,4,9,2,0,6,5,7,8,4,3,10,9,6,7,8,5,3,9,1,2,7,8}

Пример 2:

`List<int> list2 = new List<int> {0,1,1,2,2,2,3,3,4,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,8,8,9,9,9,9,10};`

• Убедитесь: я использую этот метод, что это не самый эффективный и элегантный фрагмент кода, который у меня естьсделал, но он работает:

  public bool TestShuffle<T>(IEnumerable<T> input)
  {
      bool satisfied = true;
      int prev1 = 0; int prev2 = 0;
      int next1 = 0; int next2 = 0;
      int i = 0;
      while (i < input.Count() && satisfied)
      {
          prev1 = i - 1; prev2 = i - 2; next1 = i + 1; next2 = i + 2;
          if (i == 0)
          {
              prev1 = input.Count() - 1;
              prev2 = prev1 - 1;
          }
          else if (i == 1)
              prev2 = input.Count() - 1;
          if (i == (input.Count() - 1))
          {
              next1 = 0;
              next2 = 1;
          }
          if (i == (input.Count() - 2))
              next2 = 0;
          satisfied =
                  (!input.ElementAt(i).Equals(input.ElementAt(prev1)))
              && (!input.ElementAt(i).Equals(input.ElementAt(prev2)))
              && (!input.ElementAt(i).Equals(input.ElementAt(next1)))
              && (!input.ElementAt(i).Equals(input.ElementAt(next2)))
          ;
          if (satisfied == false)
              Console.WriteLine("TestShuffle fails at " + i);
          i++;
      }
      return satisfied;
  }
  

РЕДАКТИРОВАТЬ 3:

Еще один тестовый ввод, который иногда дает сбой:

List<int> list3 = new List<int>(){0,1,1,2,2,3,3,3,4,4,4,5,5,5,5,6,6,6,6,7,7,7,8,8,8,8,9,9,9,9,10,10};

Answer 1

Оптимизированная версия

К моему разочарованию, моя оптимизированная функция работает только в 7 раз быстрее, чем простая версия LINQ.Неоптимизированный LINQ 1m43s Оптимизированный 14,7s .

• linux 32-битный
• Mono 2.11 (C # 4.0) с компилятором -optimize+,
• 1 000 000 TESTITERATIONS
• VERBOSE не #define -d

Что было оптимизировано:

• предполагать массивыдля ввода и вывода
• работа на месте с массивом ввода
• «ручной» анализ прогонов идентичных значений вместо использования GroupBy (с использованием ValueRun struct)
• иметь эти ValueRun структуры в массиве вместо перечисляемого (список);сортировка / перемешивание на месте
• использование unsafe блоков и указателей ( без заметной разницы ... )
• использование индексации по модулю вместо MAGIC кода Linq
• генерирует вывод путем итеративного добавления вместо вложенного LINQ. Это, вероятно, оказало наибольшее влияние.На самом деле, было бы еще лучше, если бы мы могли сократить число ValueRun с коллекцией countruns, упорядоченной по этому количеству, это было довольно легко сделать;однако транспонированное индексирование (необходимое для циклических ограничений) усложняет ситуацию.Выгода от применения этой оптимизации в любом случае будет больше при больших входных данных и множестве уникальных значений и некоторых сильно дублированных значений.

Вот код с оптимизированной версией._Дополнительный прирост скорости можно получить, сняв засев RNG;они предназначены только для возможности регрессионного тестирования выходных данных.

[... old code removed as well ...]

---

Исходный ответ (частичный)

Если я вас правильно понял, вы пытаетесь придумать случайное перемешивание, которое не дает дубликатам заканчиваться последовательным выводом (с минимальным перемежением из 2 элементов).

Это не решаемов общем случае.Представьте себе ввод только идентичных элементов:)

Обновление: проблемное положение вещей

Как я уже упоминал в заметках, я думаю, что я не всегда был на правильном пути.Либо я должен ссылаться на теорию графов (кто-нибудь?), Либо использовать вместо этого простой алгоритм «брутфорси», очень длинное предложение Эрика.проблемы (включите случайные образцы, чтобы быстро увидеть проблемы):

#define OUTPUT       // to display the testcase results
#define VERIFY       // to selfcheck internals and verify results
#define SIMPLERANDOM
// #define DEBUG        // to really traces the internals
using System;
using System.Linq;
using System.Collections.Generic;

public static class Q5899274
{
    // TEST DRIVER CODE
    private const int TESTITERATIONS = 100000;
    public static int Main(string[] args)
    {
        var testcases = new [] {
            new [] {0,1,1,2,2,2,3,3,4,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,8,8,9,9,9,9,10},
            new [] {0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,6,6,6,7,7,7,7,8,8,8,8,9,9,9,9,9,10},
            new [] { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41, 42, 42, 42, },
            new [] {1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4},
        }.AsEnumerable();

        // // creating some very random testcases
        // testcases = Enumerable.Range(0, 10000).Select(nr => Enumerable.Range(GROUPWIDTH, _seeder.Next(GROUPWIDTH, 400)).Select(el => _seeder.Next(-40, 40)).ToArray());

        foreach (var testcase in testcases)
        {
            // _seeder = new Random(45); for (int i=0; i<TESTITERATIONS; i++) // for benchmarking/regression
            {
                try
                {
                    var output = TestOptimized(testcase);
#if OUTPUT
                    Console.WriteLine("spread\t{0}", string.Join(", ", output));
#endif
#if VERIFY
                    AssertValidOutput(output);
#endif
                } catch(Exception e)
                {
                    Console.Error.WriteLine("Exception for input {0}:", string.Join(", ", testcase));
                    Console.Error.WriteLine("Sequence length {0}: {1} groups and remainder {2}", testcase.Count(), (testcase.Count()+GROUPWIDTH-1)/GROUPWIDTH, testcase.Count() % GROUPWIDTH);
                    Console.Error.WriteLine("Analysis: \n\t{0}", string.Join("\n\t", InternalAnalyzeInputRuns(testcase)));
                    Console.Error.WriteLine(e);
                }
            }
        }

        return 0;
    }

#region Algorithm Core
    const int GROUPWIDTH = 3; /* implying a minimum distance of 2
                                 (GROUPWIDTH-1) values in between duplicates
                                 must be guaranteed*/

    public static T[] TestOptimized<T>(T[] input, bool doShuffle = false)
        where T: IComparable<T>
    {
        if (input.Length==0)
            return input;

        var runs = InternalAnalyzeInputRuns(input);
#if VERIFY
        CanBeSatisfied(input.Length, runs); // throws NoValidOrderingExists if not
#endif
        var transpositions = CreateTranspositionIndex(input.Length, runs);

        int pos = 0;
        for (int run=0; run<runs.Length; run++)
            for (int i=0; i<runs[run].runlength; i++)
                input[transpositions[pos++]] = runs[run].value;

        return input;
    }

    private static ValueRun<T>[] InternalAnalyzeInputRuns<T>(T[] input)
    {
        var listOfRuns = new List<ValueRun<T>>();
        Array.Sort(input);
        ValueRun<T> current = new ValueRun<T> { value = input[0], runlength = 1 };

        for (int i=1; i<=input.Length; i++)
        {
            if (i<input.Length && input[i].Equals(current.value))
                current.runlength++;
            else
            {
                listOfRuns.Add(current);
                if (i<input.Length)
                    current = new ValueRun<T> { value = input[i], runlength = 1 };
            }
        }

#if SIMPLERANDOM
        var rng = new Random(_seeder.Next());
        listOfRuns.ForEach(run => run.tag = rng.Next()); // this shuffles them
#endif
        var runs = listOfRuns.ToArray();
        Array.Sort(runs);

        return runs;
    }

    // NOTE: suboptimal performance 
    //   * some steps can be done inline with CreateTranspositionIndex for
    //   efficiency
    private class NoValidOrderingExists : Exception { public NoValidOrderingExists(string message) : base(message) { } }
    private static bool CanBeSatisfied<T>(int length, ValueRun<T>[] runs)
    {
        int groups = (length+GROUPWIDTH-1)/GROUPWIDTH;
        int remainder = length % GROUPWIDTH;

        // elementary checks
        if (length<GROUPWIDTH)
            throw new NoValidOrderingExists(string.Format("Input sequence shorter ({0}) than single group of {1})", length, GROUPWIDTH));
        if (runs.Length<GROUPWIDTH)
            throw new NoValidOrderingExists(string.Format("Insufficient distinct values ({0}) in input sequence to fill a single group of {1})", runs.Length, GROUPWIDTH));

        int effectivewidth = Math.Min(GROUPWIDTH, length);

        // check for a direct exhaustion by repeating a single value more than the available number of groups (for the relevant groupmember if there is a remainder group)
        for (int groupmember=0; groupmember<effectivewidth; groupmember++)
        {
            int capacity = remainder==0? groups : groups -1;

            if (capacity < runs[groupmember].runlength)
                throw new NoValidOrderingExists(string.Format("Capacity exceeded on groupmember index {0} with capacity of {1} elements, (runlength {2} in run of '{3}'))",
                            groupmember, capacity, runs[groupmember].runlength, runs[groupmember].value));
        }

        // with the above, no single ValueRun should be a problem; however, due
        // to space exhaustion duplicates could end up being squeezed into the
        // 'remainder' group, which could be an incomplete group; 
        // In particular, if the smallest ValueRun (tail) has a runlength>1
        // _and_ there is an imcomplete remainder group, there is a problem
        if (runs.Last().runlength>1 && (0!=remainder))
            throw new NoValidOrderingExists("Smallest ValueRun would spill into trailing incomplete group");

        return true;
    }

    // will also verify solvability of input sequence
    private static int[] CreateTranspositionIndex<T>(int length, ValueRun<T>[] runs)
        where T: IComparable<T>
    {
        int remainder = length % GROUPWIDTH;

        int effectivewidth = Math.Min(GROUPWIDTH, length);

        var transpositions = new int[length];
        {
            int outit = 0;
            for (int groupmember=0; groupmember<effectivewidth; groupmember++)
                for (int pos=groupmember; outit<length && pos<(length-remainder) /* avoid the remainder */; pos+=GROUPWIDTH)
                    transpositions[outit++] = pos;

            while (outit<length)
            {
                transpositions[outit] = outit;
                outit += 1;
            }

#if DEBUG
            int groups = (length+GROUPWIDTH-1)/GROUPWIDTH;
            Console.WriteLine("Natural transpositions ({1} elements in {0} groups, remainder {2}): ", groups, length, remainder);
            Console.WriteLine("\t{0}", string.Join(" ", transpositions));
            var sum1 = string.Join(":", Enumerable.Range(0, length));
            var sum2 = string.Join(":", transpositions.OrderBy(i=>i));
            if (sum1!=sum2)
                throw new ArgumentException("transpositions do not cover range\n\tsum1 = " + sum1 + "\n\tsum2 = " + sum2);
#endif
        }

        return transpositions;
    }

#endregion // Algorithm Core

#region Utilities
    private struct ValueRun<T> : IComparable<ValueRun<T>>
    {
        public T value;
        public int runlength;
        public int tag;         // set to random for shuffling

        public int CompareTo(ValueRun<T> other) { var res = other.runlength.CompareTo(runlength); return 0==res? tag.CompareTo(other.tag) : res; }
        public override string ToString() { return string.Format("[{0}x {1}]", runlength, value); }
    }

    private static /*readonly*/ Random _seeder = new Random(45);
#endregion // Utilities

#region Error detection/verification
    public static void AssertValidOutput<T>(IEnumerable<T> output)
        where T:IComparable<T>
    {
        var repl = output.Concat(output.Take(GROUPWIDTH)).ToArray();

        for (int i=1; i<repl.Length; i++) 
            for (int j=Math.Max(0, i-(GROUPWIDTH-1)); j<i; j++)
                if (repl[i].Equals(repl[j]))
                    throw new ArgumentException(String.Format("Improper duplicate distance found: (#{0};#{1}) out of {2}: value is '{3}'", j, i, output.Count(), repl[j]));
    }
#endregion

}

Answer 2

Ваши требования исключают альтернативу real shuffling : здесь нет случайности или есть контролируемая случайность. Вот один особый подход

1. Сортировка по оригинальному списку L
2. Найти режим M и его частоту n
3. Если n чётно, n ++.
4. Создание k (= 5 *n - 1) списков (от простого до n и 5 раз n) L ₁ до L _k
   (5 выбран, чтобы избежать двух предыдущих элементов и двух следующих элементов)
5. Назначить все элементы в списки k в циклическом порядке
6. По отдельности перемешать все списки k.
7. Соберите содержимое списков k в следующем порядке: а. выберите случайным образом +5 или -5 как x.
   б. выберите случайное число j.
   с. повторите k раз:
   я. добавить все содержимое из L _j .
   II. j <- (<code>j + x) мод k

[5, 6, 7, 7, 8, 8, 9, 10, 12, 13, 13, 14, 14, 14, 17, 18, 18, 19, 19, 20, 21, 21, 21, 21, 24, 24, 26, 26, 26, 27, 27, 27, 29, 29, 30, 31, 31, 31, 31, 32, 32, 32, 33, 35, 35, 37, 38, 39, 40, 42, 43, 44, 44, 46, 46, 47, 48, 50, 50, 50, 50, 51, 52, 53, 54, 55, 56, 57, 57, 58, 60, 60, 60, 61, 62, 63, 63, 64, 64, 65, 65, 65, 68, 71, 71, 72, 72, 73, 74, 74, 74, 74, 75, 76, 76, 76, 77, 77, 77, 78, 78, 78, 79, 79, 80, 81, 82, 86, 88, 88, 89, 89, 90, 91, 92, 92, 92, 93, 93, 94, 94, 95, 96, 99, 99, 100, 102, 102, 103, 103, 105, 106, 106, 107, 108, 113, 115, 116, 118, 119, 123, 124, 125, 127, 127, 127, 128, 131, 133, 133, 134, 135, 135, 135, 137, 137, 137, 138, 139, 141, 143, 143, 143, 145, 146, 147, 153, 156, 157, 158, 160, 164, 166, 170, 173, 175, 181, 181, 184, 185, 187, 188, 190, 200, 200, 215, 217, 234, 238, 240]

Частота режима = 4, поэтому 19 слотов (# 0 - # 18)

0: [7, 21, 32, 50, 65, 77, 93, 115, 137, 173]
1: [8, 21, 33, 51, 65, 78, 93, 116, 137, 175]
2: [8, 24, 35, 52, 65, 78, 94, 118, 138, 181]
3: [9, 24, 35, 53, 68, 78, 94, 119, 139, 181]
4: [10, 26, 37, 54, 71, 79, 95, 123, 141, 184]
5: [12, 26, 38, 55, 71, 79, 96, 124, 143, 185]
6: [13, 26, 39, 56, 72, 80, 99, 125, 143, 187]
7: [13, 27, 40, 57, 72, 81, 99, 127, 143, 188]
8: [14, 27, 42, 57, 73, 82, 100, 127, 145, 190]
9: [14, 27, 43, 58, 74, 86, 102, 127, 146, 200]
10: [14, 29, 44, 60, 74, 88, 102, 128, 147, 200]
11: [17, 29, 44, 60, 74, 88, 103, 131, 153, 215]
12: [18, 30, 46, 60, 74, 89, 103, 133, 156, 217]
13: [18, 31, 46, 61, 75, 89, 105, 133, 157, 234]
14: [19, 31, 47, 62, 76, 90, 106, 134, 158, 238]
15: [19, 31, 48, 63, 76, 91, 106, 135, 160, 240]
16: [5, 20, 31, 50, 63, 76, 92, 107, 135, 164]
17: [6, 21, 32, 50, 64, 77, 92, 108, 135, 166]
18: [7, 21, 32, 50, 64, 77, 92, 113, 137, 170]

Перестановка отдельных списков и выбор списков на 5 слотов друг от друга (случайным образом начинаются с # 16):

16: [31, 135, 92, 76, 107, 5, 164, 63, 20, 50]
2: [52, 24, 35, 78, 181, 8, 138, 94, 118, 65]
7: [57, 143, 99, 81, 40, 13, 127, 72, 188, 27]
12: [46, 30, 60, 89, 133, 74, 156, 18, 103, 217]
17: [64, 50, 135, 92, 21, 32, 108, 77, 166, 6]
3: [9, 94, 181, 119, 24, 35, 139, 68, 53, 78]
8: [145, 27, 14, 57, 42, 100, 190, 82, 73, 127]
13: [89, 18, 75, 61, 157, 234, 133, 105, 31, 46]
18: [113, 21, 7, 92, 64, 32, 137, 50, 170, 77]
4: [71, 10, 37, 26, 123, 54, 184, 79, 95, 141]
9: [27, 74, 86, 14, 102, 146, 127, 43, 58, 200]
14: [62, 106, 158, 134, 19, 47, 238, 31, 76, 90]
0: [7, 77, 65, 21, 50, 93, 173, 115, 32, 137]
5: [96, 79, 26, 185, 12, 71, 124, 143, 55, 38]
10: [29, 14, 147, 60, 128, 88, 74, 44, 102, 200]
15: [106, 240, 63, 48, 91, 19, 160, 31, 76, 135]
1: [65, 33, 21, 51, 137, 8, 175, 93, 116, 78]
6: [143, 26, 13, 56, 99, 72, 39, 80, 187, 125]
11: [103, 88, 29, 60, 74, 44, 17, 153, 131, 215]

[31, 135, 92, 76, 107, 5, 164, 63, 20, 50,52, 24, 35, 78, 181, 8, 138, 94, 118, 65, 57, 143, 99, 81, 40, 13, 127, 72, 188, 27, 46, 30, 60, 89, 133,74, 156, 18, 103, 217, 64, 50, 135, 92, 21, 32, 108, 77, 166, 6, 9, 94, 181, 119, 24, 35, 139, 68, 53, 78,145, 27, 14, 57, 42, 100, 190, 82, 73, 127, 89, 18, 75, 61, 157, 234, 133, 105, 31, 46, 113, 21, 7, 92, 64,32, 137, 50, 170, 77, 71, 10, 37, 26, 123, 54, 184, 79, 95, 141, 27, 74, 86, 14, 102, 146, 127, 43, 58, 200,62, 106, 158, 134, 19, 47, 238, 31, 76, 90, 7, 77, 65, 21, 50, 93, 173, 115, 32, 137, 96, 79, 26, 185, 12,71, 124, 143, 55, 38, 29, 14, 147, 60, 128, 88, 74, 44, 102, 200, 106, 240, 63, 48, 91, 19, 160, 31, 76, 135,65, 33, 21, 51, 137, 8, 175, 93, 116, 78, 143, 26, 13, 56, 99, 72, 39, 80, 187, 125, 103, 88, 29, 60, 74,44, 17, 153, 131, 215]

Answer 3

Это может быть выполнено с помощью простого, двухэтапного процесса.Сначала используйте перетасовку Фишера-Йейтса (Кнута) на месте.Затем выполните итерацию по списку один раз, копируя его элементы в новый список.Когда вы столкнетесь с элементом, вставьте его в первую легальную позицию в вашем новом списке.(Это будет намного более эффективно при использовании связанного списка, чем при использовании массива в качестве пункта назначения.) Если нет юридической позиции для вставки, экземпляр проблемы будет неразрешимым.Если вам удастся заполнить список получателей, проблема решена.Это займет O (n) в лучшем случае и O (n ^ 2) в худшем.

Answer 4

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