Minimiser le nombre d'extractions égaux consécutifs dans une file double de la carte

Question

J'espère que cet endroit est le meilleur pour ce genre de question.

J'ai le problème suivant (je pense est plus complexe qu'il n'y paraît).

J'utilise une file d'attente à double extrémité (deque) structure de données de chaînes de caractères. deque extractions;

Le deque ne contient que N différentes chaînes, chaque chaîne répétée pour M fois dans un ordre aléatoire, de telle sorte que la longueur de la deque est N * M, par exemple, supposons que M = 4, N = 2, string1 = "A" , chaine2 = "B":

extractions[1] = "A"
extractions[2] = "A"
extractions[3] = "B"
extractions[4] = "B"
extractions[5] = "A"
extractions[6] = "B"
extractions[7] = "B"
extractions[8] = "A"

Je suis à la recherche d'un algorithme qui me permet de trouver une configuration intéressante dans laquelle il n'y a pas deux éléments égaux consécutifs, dans ce cas, il devrait y avoir que deux solutions, le « A », « B », » A " "B", "A", "B", "A", "B" et "B", "A", "B", "A", "B", "A"," B ","UNE". Pour une configuration « intéressante » Je veux dire la configuration pas simplement donnée par un nombre N de boucles imbriquées.

Une solution très stupide que j'ai mis en est de mélanger au hasard la plate-forme avec std::random_shuffle jusqu'à ce qu'aucun des éléments égaux occurence consécutifs se trouve, mais cela est à la fois stupide et lent, ce qui est plus comme un ... tri stupide

Il est clair que maximiser la distance d'édition entre les chaînes devrait être mieux. Certains indice?

Answer 1

Commencer avec une configuration trivial, par exemple pour N = 4, un M = 4, début de

A B C D A B C D A B C D A B C D

et puis exécutez un algorithme de mélange standard, mais en observant la contrainte que vous n'apporter deux éléments égaux à côté les uns des autres, i.e..

for i = 0 .. N*M - 2
  let j = random(N*M - 2 - i) + i + 1
    if ((i == 0 || array[i - 1] != array[j])
        && (array[i + 1] != array[j])
        && (array[i] != array[j - 1])
        && (j == N*M - 1 || array[i] != array[j + 1]))
      swap (array[i], array[j])

Cela devrait vous laisser très rapidement avec une configuration aléatoire qui répond à vos besoins de ne pas avoir deux éléments égaux consécutifs.

Answer 2

int total = m * n;

for (int i = 1; i < total - 1; i++)
  {
    int j = total - 1;
    while ((j > i) && (queue[i - 1] == queue[j]))
      j--;
    if (queue[i - 1] == queue[j])
      {
        String aux = queue[i - 1];
        queue[i - 1] = queue[j];
        queue[j] = aux;
      }
  }

Ce code n'est pas testé, mais vous voyez l'idée.

Answer 3

Je le ferais avec récursion:

exemple en C #: Je trouve plus « parlant » que les boucles imbriquées:

public List<String> GetPermutations(string s, IEnumerable<String> parts, string lastPart, int targetLength)
{
    List<String> possibilities = new List<string>();

    if (s.Length >= targetLength)
    {
        possibilities.Add(s);
        return possibilities;
    }

    foreach (String part in parts)
    {
        if (!part.Equals(lastPart))
        {
            possibilities.AddRange(
               GetPermutations(s + part, parts, part, targetLength));
        }
    }

    return possibilities;
}

utilisation:

List<String> parts = new List<String>() { "A", "B", "C"};
int numOccurences = 4;

List<String> results = 
    GetPermutations("", parts, "", numOccurences * parts.Count );

Mais si vous voulez juste une seule solution possible (ce qui est beaucoup plus rapide à calculer bien sûr):

il vous créer un hasard, solution non triviale comme: CACBCBCABABACAB (A, B, C)

public String GetRandomValidPermutation(
     string s, 
     List<String> parts, 
     string lastPart, 
     int targetLength)
{
    if (s.Length >= targetLength)
    {
        return s;
    }

    String next = String.Empty; 
    while(
      (next = parts[new Random().Next(0, parts.Count)])
      .Equals(lastPart)
    ){}

    return GetRandomValidPermutation(s + next, parts, next, targetLength);
}

appel:

String validString = 
    GetRandomValidPermutation("", parts, "", numOccurences * parts.Count);