alle möglichen kombinationen bekommen

[Johannes (Gast)]

Hallo,
ich möchte gerne einen array/vektor o.ä schreiben, wo ich werte 
reinschreibe
da möchte ich gerne zahlen und buchstaben reinschreiben.
nummer_1=[1,2,a,b,c]

jetzt möchte ich gerne alle möglichen kombinationen für 4 werte 
bekommen:

1,1,1,1
1,1,1,2
1,1,2,1
...
a,b,b,c
...
b,b,c,a
usw.

gibt es da regeln für? oder wie könnte ich da am besten vorgehen?
habe zunächst überlegt es mit for-schleifen zu machen. Das würde ja aber 
denke ich mal ewig dauern.

Womit ich das mache, ist eigentlich relativ egal. Am liebsten wäre mir 
jedoch c++, da ich das am besten kann.

Gruß

Johannes

[Wegstaben V. (wegstabenverbuchsler)]

rechne erst mal kombinatorisch aus, wieviele verschiedene Kombinationen 
es gibt. 26 (kleine) Buchstaben plus 10 Ziffern, ergibt 36 
Werteausprägungen.

Für 4 Stellen gibt es also 36 x 36 x 36 x 36 = 1679616 vollständige 
Kombinationen. Aber vieleicht willst du ja gar nicht alle möglichen 
Kombinationen generieren, sondern nur bestimmte Werte-Kobinationen, dann 
wirds natürlich weniger.

"Wohin"  willst du denn diese ca. 1.7 Millionen Kombinationen 
"schreiben"? In eine Datei?

Deine Ansatz

> habe zunächst überlegt es mit for-schleifen zu machen

geht schon mal in die richtige Richtung. Da du ja wie du schreibst schon 
etwas programmieren kannst:

> Am liebsten wäre mir jedoch c++, da ich das am besten kann.

zeig doch einfach mal das, was du schon hast, und was daran nicht geht.

Deine Vermutung

> Das würde ja aber denke ich mal ewig dauern.

ist (abhängig von deiner Ziel-Hardware) vermutlich vollständig 
unbegründet. Selbst wenn die Erzeugung und Abspeicherung jeder einzelnen 
Kombination ca. 1 ms (Milli-Sekunde) dauert (was für Computer eine 
Ewigkeit ist) braucht der gesamte Vorgang keine halbe Stunde - "eine 
Ewigkeit" sieht anders für mich aus. Oder hast du bestimmte Zeitvorgaben 
(z.B. "muß innerhalb von 10 Sekunden generiert werden")??

[Peter II (Gast)]

Johannes schrieb:
> habe zunächst überlegt es mit for-schleifen zu machen.
ja, das ist eigentlich üblich

[c]
int index = 0;
for( int i1 = 0; i1 < 36; ++i1 ) {
  for( int i2 = 0; i2 < 36; ++i2 ) {
     for( int i3 = 0; i3 < 36; ++i3 ) {
         for( int i4 = 0; i4 < 36; ++i4 ) {
             nummer_1[index++] = ....
         }
     }
  }
}
[/]

Das würde ja aber
> denke ich mal ewig dauern.
auf einer schnelle CPUs wird es wohl kaum länger als ein paar Sekunden 
dauern.

[Vlad T. (vlad_tepesch)]

- füll einen Vector mit deinen Werten.
- sortiere diesen
- benutze next_permutation

beliebige andere randomiterable container können auch benutzt werden:

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main() {
    std::string str = "abc012"  ;
    
    cout << "sorting String '"<<str<<"' :";
    std::sort(str.begin(), str.end());
    cout << " '"<<str<<"' :"<<endl;

    cout << "permutations: "<<endl;

    do {
        cout << str << endl;
    } while (next_permutation(str.begin(), str.end()));
    return 0;
}

WIchtig ist, es muss eine Sortierfunktion für die elemente 
bereitgestellt werden und der COntainer muss muss am Anfang sortiert 
sein, sonst kriegst du nicth alle Permutationen


Edit:
Oh ich seh gerade du willst alle Kombinationen - naja nicht richtig 
gelesen - ich lass es trotzdem mal stehen.

[Clemens S. (zoggl)]

Wenn du nur die Kombinationen aus den Zeichen im String hast must du 
zuerst zählen wie viele verscheiden zeichen du hast und wie viele 
Stellen da sind.

Danach rechnest du mit pow(N,M) aus wie viele Kombinationen das sind und 
initialisierst dein Array. N verschieden Zeichen, M Anzahl der Stellen

Feld initialisieren und am einfachsten mit for Schleifen füllen.

probiere aber auch den weg über pointer, schaun ob das schneller ist ;)

[Oliver S. (oliverso)]

Johannes schrieb:
> Das würde ja aber
> denke ich mal ewig dauern.

Das kommt auf deine Definition von "ewig" an.

Selbst wenn du alle Kombinationen als Konstanten in einem Headerfile 
ablegt, müssen die beim Programmstart in den Speicher geladen werden. 
Das mag dann etwas schneller gehen als deine for-schliefen, aber 
unendlich schnell geht das halt nicht.

Die spannende Frage ist allerdings, was du dann mit den Daten anfangen 
möchtest.

Oliver

[Vlad T. (vlad_tepesch)]

Peter II schrieb:
>

> int index = 0;
> for( int i1 = 0; i1 < 36; ++i1 ) {
>   for( int i2 = 0; i2 < 36; ++i2 ) {
>      for( int i3 = 0; i3 < 36; ++i3 ) {
>          for( int i4 = 0; i4 < 36; ++i4 ) {
>              nummer_1[index++] = ....
>          }
>      }
>   }
> }
>

das ist aber schon ziemlich hässlich (abgesehen davon, dass es nicht 
funktioniert, weil auf jeder Schleifenebene die entsprechenden Stelle 
verändert werden müsste)

for( int i1 = 0; i1 < 36; ++i1 ) {
  nummer_1[0] = i1;
  for( int i2 = 0; i2 < 36; ++i2 ) {
     nummer_1[1] = i2;
     for( int i3 = 0; i3 < 36; ++i3 ) {
         nummer_1[2] = i3;
         for( int i4 = 0; i4 < 36; ++i4 ) {
             nummer_1[3] = i4;
             // hier noch output
         }
     }
  }
}

aber wie gesagt, das ist ja beschränkt auf eine spezielle breite.

hier eins für variable outputlängen:

#include <iostream>
#include <vector>
#include <list>

std::string buildString(const std::vector<int>& vec, const std::string& alphabet){
  std::string res(vec.size(), '-');
  for(int i=0; i<vec.size(); ++i){
    res[i] = alphabet[vec[i]];
  }
  return res;
}

int main(){

  const int outputLength = 4;
  const std::string alphabet("abc123");
  const int symCount = alphabet.length();

  std::vector<int> curCombination(outputLength, 0);
  std::list<std::string> combinations;


  int pos;
  do{
    for(int i=0; i<symCount; ++i){
      curCombination[0] = i;
      combinations.push_back(buildString(curCombination, alphabet));
    }
    pos=1;
    while(pos < outputLength){
     curCombination[pos]++;
     if(curCombination[pos]>=symCount){
       curCombination[pos] = 0;
       pos++;
     }else{
       break;
     }
    }  

  }while(pos < outputLength);
  
  
  /* output generated list */
  auto it  = combinations.begin();
  auto ite = combinations.end();
  for( ; it!=ite; ++it){
    std::cout << *it << std::endl;
  }
  
  return 0;
}

kann man hier testen:
http://ideone.com/wyu3HR

output (gekürzt):

    aaaa
    baaa
    caaa
    1aaa
    2aaa
    3aaa
    abaa
    bbaa
    cbaa
    1baa
    2baa
    3baa
[...]
    c233
    1233
    2233
    3233
    a333
    b333
    c333
    1333
    2333
    3333

will man zusätzlich alle Kombinationen der Längen < Outputlength muss 
man halt einfach noch eine geeignete Schleife ringsrum machen.

[MaWin (Gast)]

Peter II schrieb:
>> denke ich mal ewig dauern.

Das liegt in der Natur der Sache, es gibt halt viele Kombinationen und 
du willst ja unbedingt jede 1 mal.

Da kann man nichts optimieren, du kannst nur deine Ansprüche 
runterschrauben, zumal: Wo willst du die 1.6 Millionen Kombinationen 
speichern ?

[Tom (Gast)]

>Womit ich das mache, ist eigentlich relativ egal.
In Hochsprachen gibt es eine Funktion für das kartesische Produkt, z.B.

#!/usr/bin/python3
from itertools import product

nummer_1=['1', '2', 'a', 'b', 'c']
for a in product(nummer_1, repeat=4):
    print(a)

[Peter II (Gast)]

MaWin schrieb:#
> Peter II schrieb:
> >> denke ich mal ewig dauern.

das habe ich nicht geschrieben.


> Wo willst du die 1.6 Millionen Kombinationen
> speichern ?

Wir gehen einfach mal davon aus, das jeder PC 10MByte Ram dafür hat.

[Tom (Gast)]

Spaßfakt: Die obige C++-Orgie für variable Längen auf a...z 0..9 
erweitert:

time ./a.out  | wc -l
1679616

real  0m3.539s
user  0m1.604s
sys  0m4.528s

Die langsame Pythonlösung in drei Zeilen (sortiert die Ausgabe von vorne 
alphabetisch):

$time ./product.py  | wc -l
1679616

real  0m3.177s
user  0m3.184s
sys  0m0.032s

Nachtrag, um fair zu bleiben:
Das std:endl ist das Problem des C++-Codes. Mit einem "\n" läuft er in 
0.8s ;)

[Tom (Gast)]

Jetzt mit verschwundenem Anhang.

[Vlad T. (vlad_tepesch)]

Tom schrieb:
> Nachtrag, um fair zu bleiben:
> Das std:endl ist das Problem des C++-Codes. Mit einem "\n" läuft er in
> 0.8s ;)

der Code ist auch alles andere als optimal.

schließlich wird im inneren jedes mal ein String gebaut und in eine 
Liste geschmissen.

      combinations.push_back(buildString(curCombination, alphabet));

schreibt man die Daten direkt in einen großen speicher und gibt den am 
Schluss aus, sollte es nochmal viel schneller gehen:


am Anfang irgendwo:

#include <iostream>
#include <vector>
#include <cmath>

int main(){

  const int outputLength = 4;
  const std::string alphabet("abc123");
  const int symCount = alphabet.length();

  std::vector<int> curCombination(outputLength, 0);
  int combinations = pow(symCount, outputLength);
  char* outputDataBuffer = new char[combinations* (outputLength+1)+1];
  char* outputDataPtr    = outputDataBuffer;



  int pos;
  do{
    for(int i=0; i<symCount; ++i){
      curCombination[0] = i;
      for(int j=0; j<outputLength; ++j){
        *outputDataPtr = alphabet[curCombination[j]];
        outputDataPtr++;
      }
      *outputDataPtr = '\n';
      outputDataPtr++;
    }
    pos=1;
    while(pos < outputLength){
     curCombination[pos]++;
     if(curCombination[pos]>=symCount){
       curCombination[pos] = 0;
       pos++;
     }else{
       break;
     }
    }  

  }while(pos < outputLength);
  *outputDataPtr = '\0';
  /* output generated data */
  std::cout << outputDataBuffer <<std::endl;
  delete[] outputDataBuffer;
  
  return 0;
}

ist aber jetzt kein hübsches c++ mehr.
mit Optimierung übersetzt sollten die Zugriffsoperatoren der std::string 
und der std::vector keinen Einfluss haben, die könnte man natürlich auch 
noch durch plain-C ersetzen.

[Oliver S. (oliverso)]

Vlad Tepesch schrieb:
> hübsches c++

Aktuelles (aber noch unhübscheres) C++ wäre die Formulierung mit 
Templates, mit denen der Ergebnisvektor zu Compilezeit ausgefüllt wird. 
Dann ird zwar das Compilieren ewig dauern, falls es überhaupt 
compilierbar ist (und ewig ist dann wirklich ewig...), aber zur Laufzeit 
ist es dann maximal schnell.

Oliver

[Tom (Gast)]

Vlad Tepesch schrieb:
> der Code ist auch alles andere als optimal.
Die neue Variante (mit -O3) läuft bei mir in 0.07s, wobei wahrscheinlich 
das Zeilenzählen mit wc -l langsam signifikant wird.

Wieder ein lehrreicher Thread. Dass das std::endl, das jeder für 
Zeilenumbrüche benutzt, sich so stark auswirkt, wenn man ernsthafte 
Datenmengen nach stdout schreibt, war mir nicht bewusst.

Mein Fazit:
1) Aktuelle Computer/Compiler sind brutal schnell (wenn sie qualifiziert 
benutzt werden). 10MByte Daten sind Peanuts und deren Berechnung 
passiert in ein paar ms. (von den 70ms nehmen wahrscheinlich die Ausgabe 
und Weiterverarbeitung den größten Teil in Anspruch.)

2) Mit Kenntnissen einer dynamischen High-Level-Sprache hat man bei 
vielen Problemen eine Lösung in ein paar Augenblicken/Zeilen 
heruntergetippt.

Für ein Einweg-Tool, das einmal eine Text-Datei mit den 16 Mio 
Kombinationen füllen soll, ist die optimierte C++-Lösung genauso 
unpassend wie der Python-Dreizeiler für numerische 
Brute-Force-Simulationen.

[DirkB (Gast)]

Tom schrieb:
> Wieder ein lehrreicher Thread. Dass das std::endl, das jeder für
> Zeilenumbrüche benutzt, sich so stark auswirkt, wenn man ernsthafte
> Datenmengen nach stdout schreibt, war mir nicht bewusst.

endl macht ja auch noch ein flush

[Yalu X. (yalu) (Moderator)]

Mathematisch gesprochen, werden hier für die Menge der vorgegebenen 
Zeichen

- alle Variationen mit Wiederholung bzw.

- die Kartesische Potenz

gesucht. Unter diesen Begriffen findet man im Netz weitere Information
und auch Programmcode.

Wenn Python zu langsam ist und C++ zu viel Tipperei bedeutet, kann man
sich natürlich auch mal Haskell anschauen :)

Es gibt dort in den mitgelieferten Bibliotheken zwar keine spezielle
Funktion zur Berechnung der kartesischen Potenz, dafür aber die
allgemeinere Funktion¹ replicateM, die – wenn man sie auf eine Liste
anwendet – genau das Gewünschte tut.

Beispiel:

replicateM 2 "abc"

liefert

["aa","ab","ac","ba","bb","bc","ca","cb","cc"]

Kompletter Code, der das Gleiche tut wie die von Tom und Vlad geposteten
Programme in Python und C++:

import Control.Monad

symbole = ['0'..'9'] ++ ['a'..'z']
ergebnisse = replicateM 4 symbole

main = putStr $ unlines ergebnisse

Laufzeiten auf meinem Rechner (Ausgabe in /dev/null umgeleitet):

Python von Tom    5,216 s
C++ von Tom       1,094 s
Haskell von mir   0,389 s
C++ von Vlad      0,026 s

Das Programm von Vlad liegt nach wie vor weit vorn. Die Ausgabe erst in
einen Puffer zu schreiben und anschließend in einem Rutsch auszugeben,
bringt sehr viel. Gibt man die Ergebnisse jeweils sofort nach ihrer
Berechnung aus (also in 1679616 cout-Aufrufen), werden 0,274 s, also
etwa die zehnfache Zeit benötigt, was aber immer noch sehr schnell ist.

——————————————
¹) Allgemein führt replicateM eine Aktion n-mal in einer Monade aus
   und sammelt die Ergebnisse in einer Liste, daher auch der Name.

[Vlad T. (vlad_tepesch)]

Yalu X. schrieb:
> Laufzeiten auf meinem Rechner (Ausgabe in /dev/null umgeleitet):
> Python von Tom    5,216 s
> C++ von Tom       1,094 s
> Haskell von mir   0,389 s
> C++ von Vlad      0,026 s

das "c++ von tom" war auch von mir :) er hatte nur das Alphabet 
angepasst, was mich auch zu der Frage führt, die ich vorsichtshalber 
stellen wollte:

Ausgabelänge und Alphabet, hast du bei allen gleich gesetzt?
ICh frag nach, weil mir 26ms ziemlich schnell vorkommt.

Angenommen 2GHz *26ms = 52Mio Takte
          / 1.6Mio Kombinationen.
Macht 33 Takte pro Kombination inklusive ausgabe.
Das kommt mir sehr komisch vor.

[Yalu X. (yalu) (Moderator)]

Vlad Tepesch schrieb:
> das "c++ von tom" war auch von mir :)

Stimmt, das hatte ich übersehen.

> Ausgabelänge und Alphabet, hast du bei allen gleich gesetzt?

Ja. Mit wc -l bekomme ich bei deiner schnellen Variante 1679617
angezeigt (1 mehr als 36⁴, weil am Ende mit std::endl noch eine
Leerzeile ausgegeben wird).

> ICh frag nach, weil mir 26ms ziemlich schnell vorkommt.

Jetzt, wo mich darauf hinweist, kommt es mir auch sehr kurz vor :)

> Angenommen 2GHz *26ms = 52Mio Takte
>           / 1.6Mio Kombinationen.
> Macht 33 Takte pro Kombination inklusive ausgabe.
> Das kommt mir sehr komisch vor.

Es ist ein Pentium 4 mit 3,2 GHz. Das wären dann immerhin 50 Zyklen.
Dafür rechnet die alte CPU innerhalb eines Zyklus weniger als eine neue.

Ich habe jetzt, um die Auflösung der Zeitmessung zu verbessern, das
Programm zehnmal hintereinander aufgerufen:

time { product; product; product; product; product; product; product; product; product; product; } > /dev/null

Das braucht 264 ms, was mit den 26 ms für 1 Durchlauf gut zusammenpasst.

Vielleicht schummelt das Betriebssystem ja etwas, wenn die Ausgabe nach
/dev/null umgeleitet wird, da sie ja sowieso vernichtet wird. um dies zu
verhindern habe ich

time { product; product; product; product; product; product; product; product; product; product; } | cat > /dev/null

probiert, was immerhin 434 ms, also 82 Zyklen dauert, wobei die
Rechnzeit von cat natürlich mitgezählt wird..

Mit der Umleitung in eine Datei auf einer RAM-Disk

time { product; product; product; product; product; product; product; product; product; product; } >/tmp/output

dauert es 419 ms bzw. 80 Zyklen. Das Schreiben einer entsprechend großen
Datei mit

time dd if=/dev/zero of=/tmp/output2 bs=1000000 count=84

dauert 218 ms.

Nein, dein Programm ist wirklich sauschnell :)

[Tom (Gast)]

>[Haskell]
Faszinierend.

Mit Zwischenspeichern läuft die Python-Version ca. doppelt so schnell 
wie einzelne print().

from itertools import product
nummer_1=[x for x in '0123456789abcdefghijklmnopqrstuvwxyz']
result=[]
for a in product(nummer_1, repeat=4):
    result.append(''.join(a))
print('\n'.join(result))

Mit list comprehension (oder generator expression, das nimmt sich 
nichts) statt append sind nochmal 25% rauszuholen:

from itertools import product
nummer_1=[x for x in '0123456789abcdefghijklmnopqrstuvwxyz']
result=[''.join(a) for a in product(nummer_1, repeat=4)]
print('\n'.join(result))

Das kratzt auf meinem antiken 1.8GHz-Core2Duo fast an der Sekunde (mit
>/dev/null) Angesichts der Geschwindigkeit von Vlads Programm sind diese 
Optimierungen aber lächerlich.

[Mike Beh (Gast)]

und dann setzt du noch vor eine auszusuchende For-Schleife ein

#pragma omp parallel for

und schon freuen sich auch die anderen CPU-Kerne über eine halbe Sekunde 
Arbeit.
(beachte dabei, dass du die Ausgabe noch threadsicher machen musst, am 
besten eine Ausgabedatei pro thread und dann hinterher zusammenhängen)

[Peter II (Gast)]

Mike Beh schrieb:
> (beachte dabei, dass du die Ausgabe noch threadsicher machen musst, am
> besten eine Ausgabedatei pro thread und dann hinterher zusammenhängen)

wenn man das schöne alte printf verwende würde, gibt es keine Probleme. 
Nur bei dem std::cout.

[Vlad T. (vlad_tepesch)]

Yalu X. schrieb:
> Nein, dein Programm ist wirklich sauschnell :)

Offensichtlich aber auch dank sehr gut optimierenden Compilern

Mike Beh schrieb:
> #pragma omp parallel for

Das scheint mir kein standard c++ zu sein. Welche Compiler unterstützen 
das unter welchen Voraussetzungen?

Ich wage auch zu bezweifeln, dass das bei obigen code irgendwas bringt, 
schließlich hat eine einzelne Iteration fast nix zu tun, ist aber dafür 
höchst abhängig von der vorherigen

[Mike Beh (Gast)]

Vlad Tepesch schrieb:
> Das scheint mir kein standard c++ zu sein. Welche Compiler unterstützen
> das unter welchen Voraussetzungen?
>
> Ich wage auch zu bezweifeln, dass das bei obigen code irgendwas bringt,
> schließlich hat eine einzelne Iteration fast nix zu tun, ist aber dafür
> höchst abhängig von der vorherigen

das ist Teil von OpenMP
http://de.wikipedia.org/wiki/OpenMP

Nutze ich mit Code::Blocks mit dem GNU GCC Compiler.
Ich bin wahrlich keine Leuchte in C++, aber das funktioniert.
Wie hoch die Gewinne ggü. dem bisher dargstellten Code sind weiss ich 
nicht, müsste mal jemand mit Zeit und Muße ausprobieren. (dabei mal 
bitte die Leistung per taskmanager überwachen, ob wirklich eine 
Lastverteilung stattfindet)

Klar lohnt sich der overhead erst ab einer bestimmten Aufgaben-Größe, 
aber probieren kanns mans ja auch hier einmal.

Alternativ kann man die Aufgabe händisch in Teile der Größe 
Gesamtmenge/(Anzahl CPU-Kerne-1) teilen (hier also die äußerste 
for-Schleife) und einzelne Threads dafür starten. Dann kan man auch 
gleich die Threads den einzelnen Kernen zuweisen und die 
Prozesspriorität hoch setzen.