Mélange de la liste avec certaines conditions

Question

J'ai une liste d'éléments qui peuvent être facilement comparés en utilisant Equals() . Je dois mélanger la liste, mais ce mélange doit satisfaire une condition :

Le i'me élément shuffledList[i] ne doivent pas être égaux aux éléments à i +/- 1 ni d'éléments à i +/- 2 . La liste doit être considérée comme circulaire, c'est-à-dire que le dernier élément de la liste est suivi du premier, et vice versa.

De plus, si possible, j'aimerais vérifier si le shuffle est même possible.

Note :

J'utilise C# 4.0.

EDIT :

Sur la base de certaines réponses, je vais vous en dire un peu plus :

• La liste n'aura pas plus de 200 éléments, il n'y a donc pas de réel besoin de bonnes performances. S'il faut 2 secondes pour la calculer, ce n'est pas la meilleure chose, mais ce n'est pas non plus la fin du monde. La liste mélangée sera sauvegardée, et à moins que la liste réelle ne change, la liste mélangée sera utilisée.

• Oui, c'est un hasard "contrôlé", mais je m'attends à ce que plusieurs exécutions de cette méthode renvoient des listes mélangées différentes.

• Je ferai d'autres modifications après avoir essayé certaines des réponses ci-dessous.

EDIT 2 :

• Deux exemples de listes qui échouent avec la mise en œuvre de Sehe (les deux ont des solutions) :

Echantillon1 :

`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};`

Solution possible :

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}

Exemple 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};`

• Vérification : J'utilise cette méthode, ce n'est pas le code le plus efficace ni le plus élégant que j'ai fait, mais il fait son travail :

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

EDIT 3 :

Une autre entrée de test qui échoue parfois :

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

Version optimisée

À ma grande déception, ma fonction optimisée ne s'exécute que 7 fois plus vite que la version LINQ "simple". LINQ non optimisé 1m43s Optimisé 14.7s .

• linux 32 bits
• compilateur Mono 2.11 (C# 4.0) avec -optimize+ ,
• 1,000,000 TESTITERATIONS
• VERBOSE no #define -d

Ce qui a été optimisé :

• supposez des tableaux pour l'entrée et la sortie
• travailler sur place sur le tableau d'entrée
• analyser " manuellement " des séries de valeurs identiques, au lieu d'utiliser GroupBy (en utilisant ValueRun struct)
• ont ces ValueRun structs dans un Array au lieu d'Enumerable (List) ; trier/shuffler in-place
• utiliser unsafe et les pointeurs ( aucune différence perceptible... )
• utiliser l'indexation modulo au lieu de MAGIC Code Linq
• générer la sortie par appendice itératif au lieu de LINQ imbriqué. C'est probablement ce qui a eu le plus d'effet. En fait, ce serait encore mieux si l'on pouvait raccourcir la fonction ValueRun qui ont une collection countruns est ordonnée par ce nombre, cela semblait assez facile à faire ; cependant, l'indexation transposée (nécessaire pour les contraintes cycliques) complique les choses. Le gain de l'application de cette optimisation d'une manière ou d'une autre sera plus important avec des entrées plus grandes et de nombreuses valeurs uniques et certaines valeurs fortement dupliquées.

Voici le code avec la version optimisée. Un gain de vitesse supplémentaire peut être obtenu en supprimant l'ensemencement des RNG ; ceux-ci ne sont là que pour permettre de tester la régression de la sortie.

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

---

Réponse originale (partiel)

Si je comprends bien, vous essayez de concevoir un mélange qui empêche les doublons de se retrouver consécutifs dans la sortie (avec un entrelacement minimum de 2 éléments).

Ceci n'est pas soluble dans le cas général. Imaginez une entrée composée uniquement d'éléments identiques :)

Mise à jour : Situation troublée

Comme je le mentionne dans les notes, je pense que je n'étais pas toujours sur la bonne voie. Je devrais soit invoquer la théorie des graphes (quelqu'un ?), soit utiliser un simple algorithme "brutal" à la place, comme l'a suggéré Erick.

Bref, pour que vous puissiez voir ce que j'ai fait, et aussi quels sont les problèmes (activez les échantillons aléatoires pour voir rapidement les problèmes) :

#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

Vos exigences éliminent les un véritable brassage alternative : il n'y a pas d'aléatoire, ou il y a un aléatoire contrôlé. Voici une approche particulière

1. Trier la liste originale L
2. Trouver le mode M et sa fréquence n
3. Si n est égale, n ++.
4. Créer k (= 5* n - 1) les listes (prime à n et 5 fois n ) L ₁ par le biais de L _k
   (5 est choisi pour éviter deux éléments précédents et deux éléments suivants)
5. Assignez tous les éléments dans le k listes à la ronde
6. Mélangez individuellement tous les k listes.
7. Rassembler le contenu de k dans l'ordre suivant : a. choisir au hasard +5 ou -5 comme x .
   b. choisir un nombre aléatoire j .
   c. répéter k temps :
   i. ajouter tout le contenu de L _j .
   ii. j <- ( j + x ) mod 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]

Fréquence du mode = 4, donc 19 slots (#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]

Mélanger les listes individuelles, et choisir des listes séparées par 5 cases (commencer aléatoirement à la case 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

Cela peut se faire par un processus simple, en deux étapes. Tout d'abord, utilisez un mélange de Fisher-Yates (Knuth) en place. Puis itérer sur la liste une fois, en copiant ses éléments dans une nouvelle liste. Lorsque vous rencontrez un élément, insérez-le dans la première position légale de votre nouvelle liste. (Cette opération sera beaucoup plus efficace avec une liste liée qu'avec un tableau comme destination). S'il n'y a pas de position légale à insérer, l'instance du problème est insoluble. Si vous parvenez à remplir votre liste de destination, le problème est résolu. Cela prendra O(n) dans le meilleur des cas et O(n^2) dans le pire.

Answer 4

• permuter les 5 valides de la liste, si aucun n'est résoluble
• supprime la permutation de la liste
• créer un graphique de cycle de ce 5
• ordonner la liste (liste restante) par nombre de positions valides dans le nouveau graphe (si vous ne faites pas cela, vous pouvez vous retrouver avec un mauvais non solvable, parce que mettre des éléments qui peuvent aller sur plus de positions augmente le nombre de positions possibles des éléments avec moins)
• continuer à prélever des éléments dans la liste, ajouter des éléments au graphique du cycle à des positions valides
• s'il n'y a pas de position valide dans le graphique ou si le graphique ne peut pas être créé, continuez avec le suivant
• si le graphe est créé, retour à l'itération de départ où le graphe a été créé
• continuer à créer d'autres graphiques
• sauvegarder tous les graphiques complets dans une liste
• choisissez un élément aléatoire dans cette liste
• si la liste est vide non résoluble