Comment est-ce que je peux mélanger une liste sans aléatoire, et garantir qu'une partie des éléments apparaîtra finalement d'un côté?

Étant donné une liste d'éléments, existe-t-il un algorithme de réarrangement qui garantira qu'à terme une demi-portion sélectionnée sera d'un côté, et le reste de l'autre?Comment est-ce que je peux mélanger une liste sans aléatoire, et garantir qu'une partie des éléments apparaîtra finalement d'un côté?

Exemple: {4, 3, 10, 7, 2, 9, 6, 8, 1, 5}

Compte tenu de l'ensemble de dessus, je voudrais avoir un algorithme de mélange qui par la suite se déplace le marqués à gauche, même si l'algorithme lui-même n'a aucune idée de ce qui est et n'est pas "marqué".

{4, 3, 10, 7, 2, 9, 6, 8, 1, 5}
X X X X X

résultats acceptable serait:
{4, 10, 9, 6, 1, 3, 7, 2, 8, 5}
{1 , 9, 10, 4, 6, 2, 8, 5, 7, 3}
{1, 4, 9, 10, 6, 3, 7, 5, 8, 2} etc

Difficulté: L'algorithme ne devrait pas utiliser de nombres aléatoires pour mélanger le contenu, il devrait être un processus itératif. Alors Fisher-Yates est sorti.

Source

2010-07-21 Tim

N'est-ce pas une sorte d'algorithme quicksort? – DumbCoder

se sent comme des manigances =). Marqué une fois - positions ou nombres? – foret

Je ne vois pas comment un algorithme ignorant les marques pourrait respecter les marques. –

Est-ce que std::next_permutation() serait ce que vous voulez? (Puisqu'il crée toutes les permutations possibles, il finira par mettre le repère une fois à gauche.)

Source

2010-07-21 13:51:39 sbi

Oui, c'est en fait! Merci beaucoup - je vais coupler ceci avec un algorithme qui vérifie chaque côté de la liste après chaque permutation pour voir si les segments ont été équilibrés. – Tim

@Tim: Étant donné la vitesse à laquelle le nombre de permutations augmente avec la taille de la chaîne, il est fort probable que ce soit _très lent. –

Divisez votre liste en deux listes: signalée et non marquée. Mélangez les deux sous-listes, et mettez le drapeau d'un côté et le non-marqué de l'autre. Maintenant, vous pouvez utiliser n'importe quel algo aléatoire que vous voulez.

Source

2010-07-21 13:54:04 corsiKa

+1 bien que je l'étende pour sélectionner la moitié aléatoirement (c'est-à-dire en itérant sur l'ensemble et en supprimant chaque élément avec une probabilité d'un). Autrement, cela conduirait à changer les deux moitiés de façon répétée (et permuter chacune d'elles). –

@Dave J'ai peur de ne pas suivre. Si vous les sélectionnez d'abord au hasard, en quoi cela diffère-t-il simplement de la mélanger? Peut-être ai-je mal compris la question? – corsiKa

L'algorithme lui-même doit être aveugle à ce qui est et n'est pas marqué. Chaque résultat d'une itération sera vérifié pour la validité, et s'il n'est pas valide, le processus continue. – Tim

Quelque chose comme next_permutation fera l'affaire, et (éventuellement) ainsi quelque chose comme bogo sort. L'un ou l'autre finira par produire toutes les permutations possibles, y compris toutes les permutations que vous considérez acceptables (avec un nombre arbitraire que vous ne considérez pas).

Le tri Bogo indique que: "L'algorithme ne doit pas utiliser de nombres aléatoires pour mélanger le contenu, il doit s'agir d'un processus itératif, donc Fisher-Yates est sorti." est une fausse dichotomie. Bogo sort mélange aléatoirement et c'est itératif.

Source

2010-07-21 13:58:49

Moins une fausse dichotomie et plus d'une exigence: J'ai besoin de l'algorithme pour ne pas utiliser le caractère aléatoire, mais je ne dis pas que l'objectif ne peut pas être atteint en l'utilisant et l'itération. Au contraire, Bogosort est juste un mélange aléatoire jusqu'à ce qu'une réponse soit trouvée. Pire complexité de cas: est O (inf) et la moyenne est O (n * n!). – Tim

Je pense que vous êtes à la recherche d'un algorithme qui: * Peut être utilisé pour afficher un processus itératif à un utilisateur qui ressemble à quelque chose comme brassage * termine avec le jeu original séparé en 2 (présélectionnés) des groupes, mais classés au hasard au sein de chaque groupe

me semble que quelque chose de simple pourrait vous convenir bien prendre en compte pour vos dix chiffres et en utilisant la terminologie marquée/non marquée pour les groupes de cet algorithme:

1. Randomly select two members of the set 
2. if swapping these two members would result in a marked number 
    being moved into positions 1-5 then forget about this swap and start again 
3. Swap these elements 
4. Check if positions 1-5 have ONLY marked elements, 
    if so you are done, otherwise start again

cela ne donne pas une statistique efficace bon mélange comme Fisher-Yates mais Cela vous donne un beau look sur l'écran.

Source

2010-07-21 14:15:03 Elemental

Comment est-ce que je peux mélanger une liste sans aléatoire, et garantir qu'une partie des éléments apparaîtra finalement d'un côté?

Répondre

Questions connexes