J'ai n listes chacune de longueur m . supposons que n * m est pair. je veux obtenir une liste aléatoire avec tous les éléments, sous la contrainte que les éléments dans les emplacements i, i + 1 où i = 0,2, ..., n * m- 2 ne proviennent jamais de la même liste. edit: autre que cette contrainte je ne veux pas biaiser la distribution des listes aléatoires. autrement dit, la solution doit être équivalente à un choix aléatoire complet qui est remanié jusqu'à ce que la contrainte soit maintenue.
exemple:
liste1: a1, a2
liste2: b1, b2
liste3: c1, c2
autorisé: b1, c1, c2, a2, a1, b2
interdits: b1, c1, c2, b2, a1, a2
4 Réponses :
Une solution possible est de penser à votre ensemble de nombres comme n blocs d'article, chaque bloc ayant la longueur de m. Si vous sélectionnez au hasard pour chaque morceau exactement un élément de chaque liste, vous ne vous retrouverez jamais dans des impasses. Assurez-vous simplement que le premier élément de chaque bloc (à l'exception du premier bloc) sera d'une liste différente de celle du dernier élément du bloc précédent.
Vous pouvez également randomiser les nombres de manière itérative, en vous assurant toujours de choisir dans une liste différente de celle du numéro précédent, mais vous pouvez alors vous retrouver dans des impasses.
Enfin, une autre solution possible est de randomiser un nombre sur chaque position de manière séquentielle, mais uniquement à partir de ceux qui "peuvent y être mis", c'est-à-dire que si vous mettez un nombre, aucune des contraintes ne sera violée, c'est-à-dire vous aurez au moins une solution possible.
l'option b n'est pas bonne en raison d'impasses. l'option a je pense que la distribution est plus biaisée que la contrainte ne l'exige. J'ai édité ma question pour souligner ce point. option c - je ne sais pas en quoi elle diffère de b
@eyaler Option C est en fait une version intelligente de l'option B. tandis qu'avec l'option B vous randomisez à partir de ce qui est possible actuellement (à chaque itération), avec l'option C vous ne laissez pas le programme choisir un élément si cela signifie que le problème n'est plus résoluble (par exemple le dernier élément de la liste X, lorsque seule la liste Y a des éléments non encore choisis, au moins deux).
Une variante de b ci-dessus qui évite les impasses: à chaque étape, vous choisissez deux fois. Tout d'abord, choisissez un article au hasard. Deuxièmement, choisissez au hasard où le placer. À la Kème étape, il y a k emplacements optionnels pour placer l'élément (le nouvel élément peut être injecté entre deux éléments existants). Naturellement, vous ne choisissez que parmi les lieux autorisés. De l'argent!
Comment garantissez-vous que les contraintes sont satisfaites?
L'endroit pour ajouter le nouvel élément est choisi uniquement parmi les emplacements autorisés, donc aucune violation ne peut se produire lors de son injection à son nouvel emplacement
Alors ce ne sera pas une distribution uniformément aléatoire. La violation survenue à un moment donné peut disparaître plus tard.
agréable! quelques questions et commentaires: 1. au lieu de choisir au hasard où placer l'élément. pouvons-nous d'abord essayer de le mettre au dernier emplacement? ou peut-on toujours l'insérer dans le premier emplacement autorisé? ou ces méthodes créeraient-elles un biais? 2. choisissez-vous un élément dans une liste différente de la précédente? nous aurions besoin d'assouplir ce comportement une fois qu'il ne reste plus qu'une liste. si nous ne modifions pas les listes à chaque fois, nous pourrions avoir un placement non légitime et avoir besoin de rééchantillonner 3. en fait, même si vous changez de liste à chaque fois, vous pouvez toujours obtenir aucune insertion légitime: abbccaa et l'élément suivant est un
4. lorsque vous avez un nombre impair d'éléments dans la solution en cours de construction, il y a deux façons de faire l'appariement (le reste au début ou à la fin). Dois-je toujours en utiliser un ou y a-t-il un cas pour changer?
5. Je pense que l'innovation pour moi ici consiste à utiliser l'insertion comme une méthode efficace pour résoudre les problèmes. Cependant, cela signifie que je dois recalculer la légitimité de tous les éléments après le point d'insertion à chaque fois. la deuxième innovation pour moi est de le construire échantillon par échantillon, ce qui facilite la fixation, mais je me demande si l'exigence selon laquelle chaque étape est légitime peut bloquer les chemins vers certains états légitimes
un blocage peut se produire si tous les éléments restants appartiennent à un seul groupe.
pour éviter cela, vérifiez à chaque itération la longueur de toutes les listes
et vérifier si la liste la plus longue est plus longue que la somme de toutes les autres .
si vrai - tirez pour cette liste
De cette façon, vous ne serez jamais laissé avec une seule liste pleine
voici l'essentiel d'une tentative de résoudre ce problème en python https://gist.github.com/YontiLevin/bd32815a0ec62b920bed214921
Une méthode très simple et rapide que j'essaie est:
random shuffle
loop over the pairs in the list:
if pair is bad:
loop over the pairs in the list:
if both elements of the new pair are different than the bad pair:
swap the second elements
break
est-ce que cela trouvera toujours une solution? les solutions auront-elles la même distribution que le brassage naïf jusqu'à ce que vous trouviez une solution légitime?
Pourquoi ne pas simplement remanier jusqu'à ce que les contraintes soient satisfaites? Je pense que la probabilité de tous les satisfaire est d'au moins 1 / e pour un grand n (à cause de en.wikipedia.org/wiki/... )
cela semble prendre un temps exponentiel dans la longueur de la liste ...
Oui, désolé, pour une raison quelconque, j'ai décidé que m vaut toujours 2.