clojure - geordnete paarweise Kombination von 2 Listen

Question

Als recht neu zu clojure kämpfe ich immer noch mit seinen Funktionen. Wenn ich 2 Listen haben, sagen: „1234“ und „ABCD“ ich alle möglich zu machen, müssen Listen der Länge bestellt 4. Ausgabe ich haben will für Länge ist 4:

("1234" "123d" "12c4" "12cd" "1b34" "1b3d" "1bc4" "1bcd" 
"a234" "a23d" "a2c4" "a2cd" "ab34" "ab3d" "abc4" "abcd") 

die 2^n in Reihe abhängig von den Eingaben.

Ich habe eine der folgenden Funktionen geschrieben, um per Zufallsauswahl eine einzelne Zeichenfolge/Liste zu generieren. Das Argument [par] wäre so etwas wie [ "1234" "ABCD"]

(defn make-string [par] (let [c1 (first par) c2 (second par)] ;version 3 0.63 msec 
    (apply str (for [loc (partition 2 (interleave c1 c2)) 
        :let [ch (if (< (rand) 0.5) (first loc) (second loc))]] 
        ch)))) 

Der Ausgang 16 wird 1 von Listen sein oben bestellt. Jede der zwei Eingabelisten hat immer die gleiche Länge, sagen wir 2,3,4,5, bis zu 2^38 oder innerhalb des verfügbaren RAM. In der obigen Funktion habe ich versucht, es zu ändern, um alle geordneten Listen zu erzeugen, aber gescheitert. Hoffentlich kann mir jemand helfen. Vielen Dank.

Answer 1

Der Trick besteht darin, die Funktion rekursiv zu machen, indem sie sich bei jedem Schritt für den Rest der Liste aufruft.

können Sie so etwas wie:

(defn make-all-strings [string1 string2] 
    (if (empty? string1) 
    [""] 
    (let [char1 (first string1) 
      char2 (first string2) 
      following-strings (make-all-strings (next string1) (next string2))] 
     (concat 
     (map #(str char1 %) following-strings) 
     (map #(str char2 %) following-strings))))) 

(make-all-strings "abc" "123") 
=> ("abc" "ab3" "a2c" "a23" "1bc" "1b3" "12c" "123") 

Answer 2

Mikera richtig ist, dass man die Rekursion verwenden müssen, aber Sie können diese während zu tun ist sowohl knapper und allgemeiner - warum die Arbeit mit zwei Saiten, wenn Sie können Arbeit mit N Sequenzen?

(defn choices [colls] 
    (if (every? seq colls) 
    (for [item (map first colls) 
      sub-choice (choices (map rest colls))] 
     (cons item sub-choice)) 
    '(()))) 

(defn choose-strings [& strings] 
    (for [chars (choices strings)] 
    (apply str chars))) 

user> (choose-strings "123" "abc") 
("123" "12c" "1b3" "1bc" "a23" "a2c" "ab3" "abc") 

Dieses rekursive nested-für ist ein sehr nützliches Muster für eine Folge von Pfaden durch einen „Baum“ von Wahlmöglichkeiten zu schaffen. Ob es einen aktuellen Baum gibt oder die gleiche Auswahl immer wieder wiederholt wird, oder (wie hier) eine Reihe von N Optionen, die nicht von den vorherigen Auswahlen abhängen, ist dies ein nützliches Werkzeug, um verfügbar zu haben.

Answer 3

Sie können auch die Vorteile der cartesian-product nehmen vom clojure.math.combinatorics Paket, obwohl dies einige Pre- und Post-Transformation der Daten erfordert:

(ns your-namespace (:require clojure.math.combinatorics)) 

(defn str-combinations [s1 s2] 
    (->> 
     (map vector s1 s2) ; regroup into pairs of characters, indexwise 
     (apply clojure.math.combinatorics/cartesian-product) ; generate combinations 
     (map (partial apply str)))) ; glue seqs-of-chars back into strings 

> (str-combinations "abc" "123") 
("abc" "ab3" "a2c" "a23" "1bc" "1b3" "12c" "123") 
> 

Answer 4

Sie auch die binären Ziffern von Zahlen zwischen 0 verwenden könnte und 16, um Ihre Kombinationen zu bilden:
Wenn ein Bit Null ist, wählen Sie aus der ersten Zeichenfolge andernfalls die zweite aus.

z. 6 = 2r0110 => "1bc4", 13 = 2r1101 => "ab3d" usw.

(map (fn [n] (apply str (map #(%1 %2) 
          (map vector "1234" "abcd") 
          (map #(if (bit-test n %) 1 0) [3 2 1 0])))); binary digits 
    (range 0 16)) 
=> ("1234" "123d" "12c4" "12cd" "1b34" "1b3d" "1bc4" "1bcd" "a234" "a23d" "a2c4" "a2cd" "ab34" "ab3d" "abc4" "abcd") 

Der gleiche Ansatz zur Erzeugung von Kombinationen von mehr als 2 Strings anwenden kann.
Angenommen, Sie haben 3 Strings ("1234" "abcd" "ABCD"), dann gibt es 81 Kombinationen (3^4). Mit Basis-3 ternären Ziffern:

(defn ternary-digits [n] (reverse (map #(mod % 3) (take 4 (iterate #(quot % 3) n)))) 
(map (fn [n] (apply str (map #(%1 %2) 
          (map vector "1234" "abcd" "ABCD") 
          (ternary-digits n) 
    (range 0 81)) 

Answer 5

(def c1 "1234") 
(def c2 "abcd") 

(defn make-string [c1 c2] 
    (map #(apply str %) 
     (apply map vector 
       (map (fn [col rep] 
        (take (math/expt 2 (count c1)) 
          (cycle (apply concat 
             (map #(repeat rep %) col))))) 
        (map vector c1 c2) 
        (iterate #(* 2 %) 1))))) 

(make-string c1 c2) 
=> ("1234" "a234" "1b34" "ab34" "12c4" "a2c4" "1bc4" "abc4" "123d" "a23d" "1b3d" "ab3d" "12cd" "a2cd" "1bcd" "abcd") 

Answer 6

(defn combine-strings [a b] 
    (if (seq a) 
    (for [xs (combine-strings (rest a) (rest b)) 
      x [(first a) (first b)]] 
     (str x xs)) 
    [""])) 

Nun, da ich es geschrieben habe ich merke, es ist eine weniger generische Version des eigenen amalloiy.