[R] Liste de nombre et chemin

[mangaskiff]

Bonjour/Bonsoir,

Je sais que le titre n'est pas très claire mais je n'ai pas trouver mieux.
Voilà mon problème:

Admettons que nous disposons de X listes de nombres de Y longueur on veux trouver tout les chemins possibles et les mettre dans un tableau.

Exemple:

On a 2 listes de nombres : "2;3;4" et 7;8" les chemins possibles sont alors 2-7 , 2-8 , 3-7 , 3-8 , 4-7 ,4-8 ici Tableau[0] = "2-7" Tableau[1] = "2-8" et ainsi de suite. Le but est de trouver ces chemins dans un cas générale.

J’espère avoir été assez claire et je vous remercie d'avance pour votre aide.

EDIT:
Je viens de trouver ça en cherchant sur papier. Il semble que le nombre de chemin possible soit égale au produit du nombre de chiffres par lignes.

Exemple :

2;3;4 -> 3 chiffres
7;8 -> 2 chiffres

2*3 = 6 chemins possibles.

Je sais pas si ça peut aider mais au moins il y a quelque chose ^^

[mikell]

► Afficher le texte

Code : Tout sélectionner

$Form1 = GUICreate("Form1", 150, 310, 200, 100)
$List = GUICtrlCreateList("", 20, 20, 110, 250)
$label = GUICtrlCreateLabel("", 20, 280, 120, 20)
GUISetState()

Dim $liste1[5] = [0, 1, 2, 3, 4], $string = "", $n = 0
Dim $liste2[6] = ["x", "y", "z", "w", "v", "u"]
Dim $liste3[4] = [5, 6, 7, 8]
For $a = 0 to UBound($liste1)-1
    For $b = 0 to UBound($liste2)-1
        For $c = 0 to UBound($liste3)-1
            $string &= $liste1[$a] & $liste2 [$b] & $liste3[$c] 
            GUICtrlSetData($List, $string & "|")
            $n += 1
            $string = ""
        Next
    Next
Next
GUICtrlSetData($label, $n & "  chemins possibles")

While GUIGetMsg()<>-3
Wend
 

Marrant ce script, vu de loin on dirait un X-Wing

[mangaskiff]

Merci de ton aide je vais essayer de généraliser ce code. Je ne met pas tout de suite en résolue ça évitera de rouvrir un topic.

Edit: j'ai beau cherché je n'y arrive pas car le nombre de boucles For dépend du nombre de liste et je ne vois pas comment rendre le nombre de boucle For variable.

[mikell]

Moi non plus, et je t'avoue que celui qui donne la solution, je lui tire mon chapeau
Faudrait peut-être essayer une array à n dimensions, ou une array d'arrays

Il manque une rubrique " défis " dans ce forum

[ragnoff]

effectivement, faire varier le nombre de boucle va être un peu compliqué ...

Par contre, faire une fonction récursive paraîtrait assez adapté ...
Si j'ai le temps, je posterai un petit script pour faire cela demain. L'idée est de générer le chemin petit à petit, quelque soit la profondeur de l'appel, donc le nombre de chiffre.

Edit : En fait, j'avais le temps ce soir ...
J'ai repris le code de mikell pour la partie graphique.

Code : Tout sélectionner

$Form1 = GUICreate("Form1", 150, 310, 200, 100)
$List = GUICtrlCreateList("", 20, 20, 110, 250)
$label = GUICtrlCreateLabel("", 20, 280, 120, 20)
GUISetState()

Dim $liste1[5] = [0, 1, 2, 3, 4], $string = "", $n = 0
Dim $liste2[6] = ["x", "y", "z", "w", "v", "u"]
Dim $liste3[4] = [5, 6, 7, 8]
Dim $liste4[10] = [1,2,3,4,5,6,7,8,9,0]

$nombre_de_liste = 4
dim $listeglobale[$nombre_de_liste] ;liste regroupant toutes les listes précédentes ...
;Faire une liste de dimension 2 serait plus adapté car plus générale
$listeglobale[0] = $liste1 ; et surtout éviterait ces lignes
$listeglobale[1] = $liste2 ; qui ne sont pas généralisable ...
$listeglobale[2] = $liste3
$listeglobale[3] = $liste4

$n = 0

Func generer_chemin($tableau_en_cours,$string)
    $liste_temp = $listeglobale[$tableau_en_cours]
    for $i = 0 to UBound($liste_temp) -1
        if $tableau_en_cours = $nombre_de_liste -1 Then
            GUICtrlSetData($List, $string & $liste_temp[$i] & "|")
            $n += 1
        Else
            generer_chemin($tableau_en_cours + 1,$string & $liste_temp[$i] )
        EndIf
    Next
EndFunc

generer_chemin(0,"")
GUICtrlSetData($label, $n & "  chemins possibles")

While GUIGetMsg()<>-3
Wend

Le mieux serait quand même de passer par une liste de dimension deux ... Mais bon, comme je l'ai mis en commentaire, tout dépend de la façon dont tu as tes listes a l'origine.

[jchd]

Je relèrerais bien, mais je ça encore renforcer l'étiquette "SQLite-maniac" qui me colle au derche comme le papier au bonbon.

(Mine de rien c'est une piste mais à vue de nez, elle plus propre à faire en SQLite qu'en récursion...)
Je vois que notre mangeur de mangas y a pensé pendant que je claviottais tranquillement.

[Tlem]

P'tet qu'en passant par un tableau de liste, ce serait 'plus simple'.

Là, je suis rentré du taf un peut tard, donc j'ai peut être l'esprit pas très clair, mais demain je devrais pouvoir rentrer un peut plus tôt (peut être). ^^


Ce que je verrais bien au début :

Code : Tout sélectionner

$saList = "2;3;4#7;8"
$alist = StringSplit($saList, "#")

[sksbir]

En reprenant toutes les bonnes idées de tout le monde, voici le résultat en 20 lignes de code ( et sans sqllite, n'en déplaise à jchd, la récursivité, c'est quand même la classe )

► Afficher le texte

Code : Tout sélectionner

#Include <Array.au3>
Dim Const $LISTES[4] = [ "0,1,2,3,4" , "x,y,z,w,v,u" , "5,6,7,8" , "1,2,3,4,5,6,7,8,9,0" ]
Dim $RESULTAT[2000]
Func exploreListe($CHAINE, $INDEX)
    $SPLIT = StringSplit($LISTES[$INDEX],",",2)
    If $INDEX<UBound($LISTES)-1 Then
        For $FILS in $SPLIT
            exploreListe($CHAINE & "," & $FILS , $INDEX+1 )
        Next
    Else
        For $FILS in $SPLIT
            $RESULTAT[0]+=1
            $RESULTAT[$RESULTAT[0]]=StringTrimLeft($CHAINE & "," & $FILS,1)  ; stringtrimleft, c'est pour virer la 1ere virgule à gauche..
        Next
    EndIf
EndFunc
exploreListe("",0)
_ArrayDisplay($RESULTAT,"Résultat",$RESULTAT[0])

 

[mikell]

et surtout éviterait ces lignes ...

Bah on peut simplifier, autoit autorise l'array d'arrays

► Afficher le texte

Code : Tout sélectionner

$Form1 = GUICreate("Form1", 150, 310, 200, 100)
$List = GUICtrlCreateList("", 20, 20, 110, 250)
$label = GUICtrlCreateLabel("", 20, 280, 120, 20)
GUISetState()

Dim $liste1[5] = [0, 1, 2, 3, 4], $string = "", $n = 0, $nb_de_liste = 4
Dim $liste2[6] = ["x", "y", "z", "w", "v", "u"]
Dim $liste3[4] = [5, 6, 7, 8]
Dim $liste4[10] = [1,2,3,4,5,6,7,8,9,0]
dim $listeglobale[$nb_de_liste] = [$liste1, $liste2, $liste3, $liste4]

generer_chemin(0,"")
GUICtrlSetData($label, $n & "  chemins possibles")
While GUIGetMsg()<>-3
Wend

Func generer_chemin($tableau_en_cours, $string)
    $liste_temp = $listeglobale[$tableau_en_cours]
    for $i = 0 to UBound($liste_temp) -1
        if $tableau_en_cours = UBound($listeglobale) -1 Then
            GUICtrlSetData($List, $string & $liste_temp[$i] & "|")
            $n += 1
        Else
            generer_chemin($tableau_en_cours + 1,$string & $liste_temp[$i] )
        EndIf
    Next
EndFunc
 

[Tlem]

Pas testé, mais visiblement, je ne suis pas rentré assez tôt.
Pas grave, demain je me fait la même journée que lundi ...
Heureusement, mikell veille au grain.

[mikell]

Mais boss, je veille parce que j'ai répondu au post n°1 donc je le suis ce sujet, c'est normal
Et puis j'espérais bien que le mot 'défi' allait provoquer des réactions

Bon le principal intérêt que je vois au StringSplit est d'échapper à cette fichue limitation dans Autoit qui donne l'erreur "Too many subscripts used for an array" si on tente une array d'arrays littérale, mais curieusement, si on fait la même chose avec des handles d'arrays, là ça marche et on n'a pas d'erreur...

So an AutoIt-Array could also contain different types, even other Arrays
$Array[3]=$AnotherArray

même si

the use of an Array inside another Array will severely affect the execution speed of your script

Donc c'est concluant, bravo aux scripteurs

[Tlem]

je t'avoue que celui qui donne la solution, je lui tire mon chapeau

Donc coup de chapeau à sksbir, puisque c'est lui qui a répondu en premier.

[mikell]

En reprenant toutes les bonnes idées de tout le monde, voici le résultat ....

Bravo sksbir, mais le coup de chapeau va à ragnoff, qui a répondu en premier
En plus il utilise ma gui, donc ma sympathie lui est acquise

[Tlem]

Ha, oui pardon, c'est le premier à avoir proposer la récursion.
Donc +1.

[jchd]

Tout dépend de la combinatoire et de la durabilité. Si c'est juste pour avoir une petite liste comme celle de l'exemple, je suis OK pour la recréer au vol. Mais dès qu'on veux généraliser et taper dans N listes de K items, ça flambe vite, surtout si on veut conserver la chose.
D'ailleurs, je parlais de récursivité pendant que le post précédent arrivait.

Bon, c'est vrai qu'actuellement j'ai tendance à voir SQLite en grand car je bosse sur une base de 850 millions de rangs, rien que dans la plus grosse table.

[sksbir]

En reprenant toutes les bonnes idées de tout le monde, voici le résultat ....

Bravo sksbir, mais le coup de chapeau va à ragnoff, qui a répondu en premier
En plus il utilise ma gui, donc ma sympathie lui est acquise

je ne me suis pas caché d'avoir repris les idées de tout le monde.
Concernant la gui, pas reprise car hors sujet. On pouvait tout aussi bien utiliser filewriteline pour sortir les résultats en temps réel sur la console, mais si j'ai utilisé un tableau, c'est que dans la demande d'origine il est stipulé ceci:

...et les mettre dans un tableau

@jchd : c'est vrai qu'on va vite emplafonner la mémoire en voulant stocker dans un tableau, mais grace au calcul que je cite ici

Il semble que le nombre de chemin possible soit égale au produit du nombre de chiffres par lignes.

On peut donc dimensionner le tableau dès le départ, et surtout anticiper pendant la saisie des données et donc avant le calcul récursif afin de ne pas exploser la mémoire.

Ha, oui pardon, c'est le premier à avoir proposer la récursion.
Donc +1.

Il me semble bien que le mot exact est "récursivité". recursion étant le mot en anglais.

[mangaskiff]

Désolé du temps de réponse j'ai pas eu trop de temps avec mes exam'. Concernant le sujet je vais essayer plusieurs choses ce week-end donc je laisse encore en non-résolu juste pour la fin de la semaine. Merci encore pour toutes ces réponses.