[gelöst] Algorithmus für Permutation

[JaKlaRo]

Hallo,
folgendes Problem:
gegeben:
- eine Buchstabenkette der Länge n (mehrfaches Vorkommen einzelner Buchstaben möglich)
- eine Zahl m <= n
gesucht:
- alle Permutationen der Länge m

Soll als BASH-Skript gelöst werden.
Gesucht wird der Algorithmus, möglichst einfach beschrieben.

Es ist klar, das die Buchstabenkette in ein Array geschrieben werden, um besser darauf zugreifen zu können. Aber dann kommen die Fragen:
- Zweites Array der Länge m für die Permutationen benutzen?
- rekursives oder iteratives Verfahren?
- Anzahl der Permutationen, m! nur wenn m = n, und m über n wenn nicht sortiert?
- ...

Besten Dank
JaKlaRo

[wanne]

Hier mal für m=3

Code: Alles auswählen

function mysort { for i in "$@"; do echo "$i"; done | sort; }


##Sortiere Permutationen (auslassung)
kette=(k e t t e)
kette=( $(mysort ${kette[*]}) )

n=${#kette[*]};
m=3
echo "m=$m n=$n"
n=$(($n-1))

declare -A out
for it1 in $(seq 0 $n); do
        for it2 in $(seq $(($it1+1)) $n);do
                for it3 in $(seq $(($it2+1)) $n); do
                        out["${kette[$it1]}${kette[$it2]}${kette[$it3]}"]=1
                done
        done
done

echo ${!out[*]}


##Unsortierte
function myuniqc { for i in "$@"; do echo "$i"; done | uniq | wc -l; }

kette=(k e t t e)
n=${#kette[*]};
m=3
echo "m=$m n=$n"
n=$(($n-1))

declare -A out
for it1 in $(seq 0 $n); do
        for it2 in $(seq 0 $n);do
                for it3 in $(seq 0 $n); do
                        [ $(myuniqc $it1 $it2 $it3) == 3 ] && \
                        out["${kette[$it1]}${kette[$it2]}${kette[$it3]}"]=1
                done
        done
done

echo ${!out[*]}

Zu Teil abgekupfert von da: http://www.programmingforums.org/post20 ... post204791

Das kannst du jetzt noch für m=4, 5 und vielleicht 6 erweitern und dann gibt die bash sowieso auf.
Anmerkung Laufzeit: Θ(n^m)
Für große n und viele doppler kann man das wahrscheinlich noch optimieren.

[JaKlaRo]

@wanne
Vielen Dank für Deine Mühe, aber leider erfüllt Dein Code nicht meine Fragestellung. Ich habe kette=(a b c d e) und erhalte als Ergebnis bei Sortierte Permutation:

Code: Alles auswählen

ade acd ace bce bcd abc cde bde abe abd

aber das sind nicht alle Permutationen der Länge 3, z.B. fehlen

Code: Alles auswählen

bac d.. e..

Bei der Unsortierten Permutation ist das Ergebnis

Code: Alles auswählen

cba bae aeb bad aec ebe cbc ebd aea ebc cbe cbd eba bac aed bab dec deb dea cab cac cad cae ded ced ade aca dae acb dad dac ada acd dab cea ace ceb adc cec adb eab eac bce bcd bcb ead bca eae eda abc edc aba cde edb bde ede cdc bdb cdb bdc cda abe bda abd dbc dba dbd dbe ecd ece eca ecb dce bea dcd bec beb dca bed dcb

aber in der Zeichenkette ist jeder Buchstabe nur einmal vorhanden, daher ist

Code: Alles auswählen

ebe aea ...

unzulässig. Ich suche auch keinen fertigen Code, sondern einen Algorithmus.

[Cae]

Ein bisschen hacky, aber es funktioniert: [Edit: evlt. funktioniert das nur fuer m == n, moeglicherweise kann man das mit 'ner $(seq $m)-Subshell anstatt der eval-Subshell in den Griff bekommen. Ist mir jetzt zu spaet fuer so Feinkrams. ]

Code: Alles auswählen

$ chars='{a,b,c}'; for c in $(eval "echo $chars"); do list="$list$chars"; done; eval "echo $list"
aaa aab aac aba abb abc aca acb acc baa bab bac bba bbb bbc bca bcb bcc caa cab cac cba cbb cbc cca ccb ccc
$ 

Leider ist das auch 'ne Implementation... keine Ahnung, was ich da mache. Rekursiv? Noe. Iterativ? Jein, so ein bisschen, das macht die Shell fuer mich. Wenn ich mich nicht irre, kann's da keine Doppelten geben, ansonsten einfach

Code: Alles auswählen

| tr ' ' '\n' | sort -u | xargs

nachschalten.

Wenn ich das selbst nachbauen muesste, wuerde ich wahrscheinlich genuegend Scheifen ineinander tueten, also das rekursiv machen. Evtl. dynamisch zur Laufzeit zusammen bauen und gegen eval werfen... hacky halt, eval is evil.

Gruss Cae

--Edit: Wie oben schon vermutet, seq an der richtigen Stelle reicht aus:

Code: Alles auswählen

$ chars='{a,b,c}'; for c in $(seq 4); do list="$list$chars"; done; eval "echo $list" | tr ' ' '\n' | sort -u | xargs
aaaa aaab aaac aaba aabb aabc aaca aacb aacc abaa abab abac abba abbb abbc abca abcb abcc acaa acab acac acba acbb acbc acca accb accc baaa baab baac baba babb babc baca bacb bacc bbaa bbab bbac bbba bbbb bbbc bbca bbcb bbcc bcaa bcab bcac bcba bcbb bcbc bcca bccb bccc caaa caab caac caba cabb cabc caca cacb cacc cbaa cbab cbac cbba cbbb cbbc cbca cbcb cbcc ccaa ccab ccac ccba ccbb ccbc ccca cccb cccc
$ 

(m ist im Beispiel 4)

[wanne]

Vielen Dank für Deine Mühe, aber leider erfüllt Dein Code nicht meine Fragestellung.

Deine Fragestellung war wohl nicht exakt genug:
Unter sortierte permutationen hatte ich verstanden dass die Ziechen innerhalb der kette alphabetisch sortiert sind, nicht die Ergebnisse als ganzes.
Aber wenn du einfach nochmal mysort auf das Ergebnis ausführst, hast du ein sortiertes Ergebnis. (Dann lässt sich der Algorithmus allerdings wesentlich effizenter schreiben: Einfach Eingabe sortieren und sicherstellen, das kein Ergebnis doppelt geschrieben wird.)

aber in der Zeichenkette ist jeder Buchstabe nur einmal vorhanden, daher ist

Code: Alles auswählen

ebe aea ...

unzulässig.

Oops, Fehler in myuniqc. So stimmt's (und ist auch gleich noch wesentlich effizienter):

Code: Alles auswählen

function myuniqc { echo "$@" | tr ' ' '\n' | sort -u | wc -l;}

Ich suche auch keinen fertigen Code, sondern einen Algorithmus.

Bis ich den erklärt habe, habe ich auch ein Beispiel gepostet. War auch mehr als Beispiel zum Weiterarbeiten gedacht.

[JaKlaRo]

Deine Fragestellung war wohl nicht exakt genug:
Unter sortierte permutationen hatte ich verstanden dass die Ziechen innerhalb der kette alphabetisch sortiert sind, nicht die Ergebnisse als ganzes.

Der Begriff sortiert ist wohl irreführend. Gemeint ist, das z.B. beim Pferderennen die Reihenfolge des Zieleinlaufs von Bedeutung ist, beim Lotto hingegen nicht. Beim Pferderennen gibt es n! Möglichkeiten, beim Lotto (49 über 6) - die "Mathematiker" unter Euch verstehen das hoffentlich -, bei meiner Fragestellung liegt es dazwischen.
Der Code funktioniert, nun ich ihn noch etwas flexibler bezüglich m machen.

Besten Dank
JaKlaRo

[wanne]

Der Begriff sortiert ist wohl irreführend.

Ich glaube geordnet nennt man typischerweise das was du meinst.

Gemeint ist, das z.B. beim Pferderennen die Reihenfolge des Zieleinlaufs von Bedeutung ist

Ich finde, zumindest beim Springen sollte man auch drauf wetten dürfen, welche Perde in's Ziel kommen.

Beim Pferderennen gibt es n! Möglichkeiten, beim Lotto (49 über 6)

Bei deiner Variante maximal n!/(n-m)!. (Wenn alle Buchstaben nur einmal vorkommen.)

[JaKlaRo]

Da die Bash für mein Problem doch ungeeignet ist, hier meine Lösung in Python:

Code: Alles auswählen

#! /usr/bin/env python
# -*- coding: utf-8 -*-
#

def choose_iter(elements, length):
    for i in xrange(len(elements)):
        if length == 1:
            yield [elements[i],]
        else:
            for next in choose_iter(elements[i+1:len(elements)], length-1):
                yield [elements[i],] + next

def choose(l, k):
    return list(choose_iter(l, k))

def next_permutation(char_list):
    try:
        if len(char_list) <= 1:
            print "1"
            return False
        i = len(char_list)-2
        while char_list[i] >= char_list[i+1]:
            i=i-1
        if i < 0:
            return False
        j=len(char_list)-1
        while char_list[j] <= char_list[i]:
            j=j-1
        char_list[i], char_list[j] = char_list[j], char_list[i]
        i=i+1
        j=len(char_list)-1
        while j >= i:
            char_list[i], char_list[j] = char_list[j], char_list[i]
            i=i+1
            j=j-1
        return char_list
    except IndexError:
        return False

if __name__=="__main__":
    string="debian"
    sorted_list=sorted(string)
    for short_list in choose(sorted_list, 4):
        print short_list
        while True:
            next_perm = next_permutation(short_list)
            if next_perm == False:
                break
            else:
                print next_perm

Die Funktion choose_iter erstellt alle Kombinationen einer bestimmten Länge und next_permutation die Permutationen daraus.