Bonjour,
je dois faire du combinatoire avec une liste de string
exemple :
letters := []string{“a”, “b”, “c”, “d”}
et generer toute les combinaisons avec doublons puis sans doublons
exemple :
a ab ac ad abc abd acd abcd b ba bc bd bac
et sans doublons :
a ab ac ad abc abd acd abcd b bc bd
si vous avez de la doc la dessus je prends merci
Toi, tu fais du go 
Vu que je fais de la base de données j’ai pensé à du produit cartésien en SQL, mais tu veux faire cela pas en SQL, donc je suis tombé là dessus à partir de la recherche « produit cartésien python ».
Peut-être que cela te donnera une piste ?
Merci
En fait je m’en fiche un peu du langage tant que c’est lisible
Tout à fait, c’est pour cela que je t’ai filé un lien en Python.
En fait ce que je voulais dire, quand je te parlais de SQL, c’est que comme le SQL est un langage ensembliste, je n’aurais rien pu te montrer puisqu’un SELECT sans jointures est un produit cartésien, aucun algo n’est visible… à moins de regarder les sources en C des moteurs de base de données.
Mais le principe du produit cartésien m’a donnée l’idée de chercher ce concept dans les langages procéduraux
Apres, un produit cartésien ne donne pas les doublons. Il faudra faire autant de produits que d’élément que tu as dans la liste.
Le probleme du produit cartésien c’est qu’il donne dans le lien donné c’est qu’il ne donne que les 3 lettre …
Par exemple il donne a,b,c mais pas a ou a,b
Si ca peut t’aider je t’ai écrit vite fait la version sans doublon en Java : https://pastebin.com/K8sQ3pac
Si tu donnes [0,1,2,3] ca renvoie
[[0, 1, 2, 3], [0, 1, 2], [0, 1, 3], [0, 1], [0, 2, 3], [0, 2], [0, 3], [0], [1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
Juste parce que ca m’agace a chaque fois que je vois “de maniere agnostique” dans le titre du thread: le mot que tu cherches c’est “algorithme”
Oui mais c’est quand même marrant son expression
Cela renvois a l’idée que les langages peuvent etre des religions pour certains
Sinon j’ai ecris ca mais ca utilise trop de fonctions propre a python pour etre agnostique :
import itertools
lst2 = ["a", "b", "c","d"]
lst2 = sorted(lst2)
combs = []
lst = []
for data in lst2 :
lst.append(":"+data+":")
for i in range(1, len(lst)+1):
els = [list(x) for x in itertools.combinations(lst, i)]
combs.extend(els)
result = []
print(combs)
for data in combs :
stre = ""
for d in data :
stre = stre + d
stre = stre.replace("::",":")
stre = stre[1:]
stre = stre[:-1]
result.append(stre)
result = sorted(result)
print(result)Clairement Python est très puissant dans ce domaine. Tu ne pourras jamais être complétement agnostique, comme tu dis, et tu seras contraint d’utiliser des langages comme Python, Perl, Ruby à moins de mettre en œuvre les fonctions manquantes dans les autres langages.
Mais au bout du compte c’est toi qui choisit ton langage, ou ton projet qui te l’impose ? Après c’est plus la syntaxe de Python qui facilité l’écriture : je déteste le VBA mais ce que tu demandes doit tout à fait pouvoir s’écrire en VBA maintenant que tu as fait tes recherches algorithmiques.
Il n’y a pas beaucoup de langage qui implémente les fonctions lambdas par exemple. Tiens je tombe là dessus: la réécriture des fonctions lambdas dans différents langages !
Idéalement j’aimerai le refaire en golang pour des raisons de perf …
Parce que le combinatoire ca peut vite partir en vrille niveau perf puis par curiosité aussi …
D’un point de vue algorithmique ca m’interesse de savoir comment faire cela sans utiliser des outils tout fait.
Peut être que tu peux faire de manière récursive ?
f([]) => []
f([e]) => [e]
f([e,...]) => [e] || [e+f([...])] || [f([...])]
Par exemple f([c,d]) ça donnerai
[c] || [c+f([d]] || f(d)
=> [c,cd,d]
f([b,c,d] ça donnerai
[b] || [b+f([c,d])] || f([c,d])
=> [b] || [bc, bcd, bd] || [c, cd, d]
=> [b, bc, bcd, bd, c, cd, d]Enfin, sinon, en C# c’est pas bien compliqué, tu generes toutes les combinaisons, tu te fais un comparer et tu inseres ca dans une hashtable et zou.
Il doit aussi y avoir plus malin en jouant sur les index de ton tableau originel pour eviter directement d’inserer une lettre, puis 2, puis 3, puis 4, etc.
j’en ai fait une partie avec une API si ca interesse du monde :
import requests
# now we make the test
login_data = {
"list": ["a", "b", "c","d"],
"separator": ";",
}
r = requests.post("https://young-earth-75813.herokuapp.com/api/v1/combine", json=login_data)
print(r.status_code)
print(r.content)
b’{« result »: [« a », « a;b », « a;b;c », « a;b;c;d », « a;b;d », « a;c », « a;c;d », « a;d », « b », « b;c », « b;c;d », « b;d », « c », « c;d », « d »]}’
et le code est la :
Le probleme c’est que ca pete tres vite -_-
D’ou ma demande de maniere agnostique pour le refaire en golang …
http://stackoverflow.com/questions/43615563/combinations-in-python3-too-big
J’ai bidouillé un truc rapide en C++, c’est agnostique tant que le language supporte les opérations sur les bits. (et en plus je crois que ça marche…)
https://0bin.net/paste/mCBu4t1gIAtJENzG#r8fL5FmW+SDIVEFfY-neJ4ppKsxBUg3DyktUzq9H4uJ
En gros j’ai fait le même principe que lorsque t’apprend la notion du binaire, par ex. pour écrire tout les chiffres avec 4 bits tu alterne les 1 et les 0 :
0000
0001
0010
0011
0100
…
Là tu prend tout les chiffres avec N bits (N étant le nombre de string). Tu considère que chaque bit correspond à une string, et paf tu as tes combinaisons uniques.
Par contre dans mon code le nombre de string en entrée est limitée (je pense). Peut-être 32-64, j’en sais trop rien j’ai pas envie de dire une trop grosse connerie (mais si quelqu’un sait … ça devrait coincer au niveau de la l.37 de mon code). Bon après y a d’autres moyens de gérer la logique (certains languages ont des bitfields, etc.).
Niveau vitesse je pense que c’est correct, au pire l’algo se parallélise bien.
Je plussoie la solution SQL. Tu peux faire ça dans une base embarquée sqlite si tu n’as pas envie de persister les données plus que ça.
Comment ca sert a rien de faire ca en langage low level. Ca ira pas plus vite. Fais du go/C/C++ si tu veux mais ca sera super marginal comme amelioration par rapport a un truc comme C# ou equivalent.
Et aussi c’est pas ca que ca veut dire agnostique… arrête de massacrer ce pauvre mot