Je suis donné n chiffres et pour eux appliquer m règles sur leur commande. Les règles sont représentées dans une paire d'index et chaque paire (A, B) indique que le nombre avec index A (A-th Number) doit être après le numéro B-TH - Il ne faut pas être à côté de lui .
Ex: N = 4
1 2 3 4
M = 2
3 2
3 1
Output: 1234, 4213, 4123, 2134, 2143, 2413, 1423 ...Maybe there are even more:)
3 Réponses :
comme un indice.
Vous pouvez traiter votre ensemble de règles comme graphique. Chaque indice est un sommet, chaque règle est un bord dirigé.
tout commande correcte des chiffres (c'est-à-dire une permutation qui satisfait aux règles) correspond à un tel appelé commande topologique du graphique ci-dessus. Afin de générer des commandes valides tous de vos numéros, vous devez générer tous les commandes topologiques possibles de ce graphique.
P.s. Le premier algorithme d'ordonnance topologique donnée à la page liée Wikipedia permet déjà une solution assez simple qui énumérerait toutes les permutations valides. Cela prendra des efforts et des soins à mettre en œuvre, mais ce n'est pas la science de la fusée.
En tant que marche avant d'aller à un type topologique complet, vous pouvez au moins créer des fragments commandés pour simplifier le forçage brute. Par exemple, si les règles de la priorité sont les suivantes: 3,4 4,5 5,8 Vous savez que vous pouvez perperger [3458] avec les compensations, les insertions et l'annexe de vos entiers non contrarié par des règles de priorité (cela est bien sûr généralisé dans ce qui précède)
brute forçage serait Passer chaque permutation , qui est O (n!), Et pour chaque permutation se bouclent simplement à travers chaque règle pour confirmer qu'elles aply, qui est O (m). Cela finit sur O (n! M) qui est un peu ridicule, mais cela ne devrait pas "ne pas fonctionner" pour un tel petit ensemble.
En fait, il pouvait vérifier les règles, tout en créant des permutations. Cela couperait considérablement le temps et il se retrouverait avec un résultat.
Je suis d'accord. Si N = 8 est le plus élevé que vous devez pouvoir gérer, il ne vaut probablement pas votre temps de trouver quelque chose de mieux que de la force brute pour quelque chose comme ça.
Oui, il y a définitivement beaucoup d'optimisations faciles à apporter à une solution de force brute, mais il mentionne qu'il a des problèmes avec même cela.
Honnêtement, votre meilleur pari est de revenir en arrière et de faire fonctionner la solution de force brute. Une fois que cela est fait (et si vous avez toujours le temps, etc.), vous pouvez rechercher un meilleur algorithme.
modifier à l'électeur en bas. L'étudiant est (devrait être) essayer de faire ses devoirs à temps . Par les sons, ses devoirs sont un exercice de programmation dans lequel une solution de force brute serait adéquate. L'aider à comprendre un algorithme efficace ne résout pas son vrai problème.
Dans ce cas, il a essayé la simple approche de la force brute (que tout le monde accepte de travailler pour de petites valeurs n ) et lui éduquée prématurément pour essayer quelque chose qui est probablement plus difficile. Tout développeur expérimenté vous dira que c'est une mauvaise idée. L'élève a besoin et mérite d'être informé de la sorte, et s'il est sensible, il fera attention. Mais évidemment, c'est son choix ...
Pourriez-vous expliquer comment les n chiffres entrent dans cela? Quelle serait la réponse si le N est où {1, 2, 3, 4}?
D'après ce que je peux voir, les n chiffres que vous avez donnés ne sont pas pertinents pour la question que vous posez. Est-ce correct?
N est combien de chiffres il y a, dans ce cas n = 4 parce qu'il y a quatre nombres, 1..4.
Dans quel sens votre solution de force brute ne fonctionne-t-elle pas? Était-ce juste trop lent ou qui l'a-t-il écrasé, ou ...?
Si la bruteforcing n'a pas fonctionné, votre code est faux.