Ruby (RMXP) > Verschiedene, einzigartige, Kombinationen mehrerer Arrays ermitteln

[-KD-]

Die ganzen Enumerator-Methoden wie product, combination etc. sind erst ab Ruby 1.9 (und damit RPGMaker VXAce) verfügbar. Aber dein rekursiver Code ist noch fehlerhaft: Du suchst in jedem Schritt nach einem Element, dass noch nicht ausgewählt wurde. Dabei berücksichtigst du keine "Sackgassen", also dass du früh eine Entscheidung triffst die alle möglichen Lösungen verbaut.

Beispiel: Rufe mal deine Methode mit dem Array [[0, 1, 2], [0, 1, 2], [0]] auf. Deine Methode wird erst die 0 wählen, dann die 1 und danach feststellen, dass es keine Lösung gibt die mit 0 und 1 anfängt und abstürzen. Wenn du schon rekursiv programmierst, musst du eine ordentliche Abbruchsbedingung einbauen, damit der Algorithmus zurückgeht und eine andere Kombination ausprobiert. Das würde dann so aussehen:

Code:

class Array
  def get_combi(arr=[],index=0)
    return arr if index >= size
    self[index].each do |ta|
      unless arr.include? ta
        arr << ta
        rekursion = get_combi arr, index+1
        # Wenn nil zurückgegeben wird, ist keine Lösung mit arr möglich!
        return rekursion if rekursion
        # mache Änderung an arr wieder rückgängig für nächsten Versuch
        arr.pop
      end
    end
    return nil # abbruch
  end
end

Alternativ hier noch eine iterative Variante:

Code:

class Array
  def uniq_combi
    indizes = Array.new(size, 0)
    set = {}
    k = 0
    while k < size
      while set[self[k][indizes[k]]]
        indizes[k] += 1
        while indizes[k] >= self[k].size
          indizes[k] = 0
          k -= 1
          return nil if k < 0
          set[self[k][indizes[k]]] = false
          indizes[k] += 1
        end
      end
      set[self[k][indizes[k]]] = true
      k += 1
    end
    i= -1
    return indizes.map {|index| self[i+=1][index]}  
  end
end

[Linkey]

Hey KD,

danke für deine Antwort. Ich hatte so eine Abfrage schon in der Methode, ich hatte die Methode von der Arbeit aus aus dem Kopf, in der schnelle, getippt x)