Conteggio delle combinazioni di coppie di elementi da più liste senza ripetizione

https://stackoverflow.com/questions/983243

13-09-2019
|

Domanda

Dato lo scenario in cui ci sono più liste di coppie di elementi, per esempio:

{12,13,14,23,24}
{14,15,25}
{16,17,25,26,36}

dove 12 è una coppia di elementi di '1' e '2' (e quindi 21 è equivalente a 12), vogliamo contare il numero di modi in cui possiamo scegliere coppie di elementi da ciascuna delle liste che non singolo l'elemento viene ripetuto.È necessario selezionare una, e una sola coppia, da ogni lista.Il numero di elementi in ogni lista e il numero di liste è arbitrario, ma si può presumere che ci siano almeno due liste con almeno un paio di elementi per ogni lista.E le coppie sono realizzati con i simboli di un alfabeto finito, si supponga cifre [1-9].Inoltre, un elenco non può né contenere duplicati coppie {12,12} o {12,21}, né può contenere simmetrica coppie {11}.

Più in particolare, nell'esempio di cui sopra, se si sceglie la coppia di elementi 14 dal primo elenco, quindi l'unica scelta che abbiamo per la seconda lista è il 25 perché il 14 e 15 contenere un '1'.E, di conseguenza, l'unica scelta dalla terza lista è di 36 perché il 16 e il 17 contenere un '1', il 25 e il 26 contenere un '2'.

Qualcuno sa di un efficiente modo per contare il totale delle combinazioni di coppie di elementi, senza passare attraverso ogni permutazione di scelte e chiedendo "questa è una scelta valida?", come le liste contengono ciascuno centinaia di coppie di elementi?

AGGIORNAMENTO

Dopo aver trascorso qualche tempo con questo, ho capito che è banale per contare il numero di combinazioni quando nessuna delle liste di condividere una coppia distinta.Tuttavia, non appena una coppia distinta è condivisa tra due o più liste, la combinatoria non si applica.

Ora come ora, sto cercando di capire se c'è un modo (utilizzando combinatoria matematica e non la forza bruta) per contare il numero di combinazioni in cui ogni lista ha le stesse coppie di elementi.Per esempio:

{12,23,34,45,67}
{12,23,34,45,67}
{12,23,34,45,67}

Soluzione

Il problema è # P-completo. Questo è ancora più difficile di quanto NP-completo. E 'difficile come trovare il numero di assegnazioni soddisfacenti a un'istanza di SAT.

La riduzione è da perfetta corrispondenza . Supponiamo di avere la G = {V, E} grafico dove E, l'insieme dei bordi, è una lista di coppie di vertici (quelle coppie che sono collegate da un bordo). Quindi codificare un esempio di "coppie di voci" avendo copie |V|/2 di E. In altre parole, un certo numero di copie di E pari alla metà del numero di vertici. Ora, un "hit" nel tuo caso corrisponderebbe a |V|/2 bordi senza vertici ripetuti, il che implica che tutti i vertici |V| sono stati coperti. Questa è la definizione di un abbinamento perfetto. E ogni abbinamento perfetto sarebbe un successo -. Si tratta di una corrispondenza 1-1

Altri suggerimenti

Consente dice che ogni elemento nelle liste è un nodo in un grafico. C'è un confine tra due nodi se possono essere selezionati insieme (non hanno alcun simbolo comune). Non v'è alcun margine tra due nodi della stessa lista. Se abbiamo n elenca il problema è quello di trovare il numero di cricche di dimensione n in questo grafico. Non v'è alcuna cricca, che è più grande di n elementi. Dato che scoprire se esiste almeno una tale cricca è NP-completo Penso che questo problema è NP-completo. Vedere: http://en.wikipedia.org/wiki/Clique_problem

Come sottolineato dobbiamo dimostrare che la soluzione di questo problema può risolvere il problema Clique per dimostrare che questo è NP-completo. Se siamo in grado di contare il numero di set richiesti cioè il numero di cricche dimensione n allora sappiamo se vi sia almeno una cricca di dimensione n. Purtroppo se non c'è cricca di dimensione n, allora non sappiamo se ci siano cricche con dimensione k

Un'altra questione è se siamo in grado di rappresentare qualsiasi grafico di questo problema. Credo di sì, ma non sono sicuro su di esso.

mi sento ancora questo è NP-completo

Mentre il problema sembra abbastanza semplice potrebbe essere correlato al NP-completo Set Di Copertura Del Problema.Quindi potrebbe essere possibile che non c'è efficace per rilevare le combinazioni valide, quindi non efficace a contarli.

AGGIORNAMENTO

Ho pensato alle voci di elenco beeing coppie perché sembra avere il problema più difficile per l'attacco - è necessario controllare due proprietà di un elemento.Così ho cercato un modo per ridurre la coppia di scalari voce e ha trovato un modo.

Mappa il set di n simboli per l'insieme dei primi n numeri primi - io chiamo questa funzione M.Nel caso dei simboli 0 per 9 otteniamo la seguente mappatura e M(4) = 11 per esempio.

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} => {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}

Ora siamo in grado di mappare una coppia (n, m) utilizzando il mapping X al prodotto delle mappature di n e m.Questa sarà la coppia (2, 5) in X((2, 5)) = M(2) * M(5) = 5 * 13 = 65.

X((n, m)) = M(n) * M(m)

Il perché di tutto questo?Se abbiamo due coppie di (a, b) e (c, d) da due liste, la mappa per loro utilizzando il mapping X per x e y e le moltiplica, si ottiene il prodotto x * y = M(a) * M(b) * M(c) * M(d) - un prodotto di quattro numeri primi.Siamo in grado di estendere il prodotto di più fattori selezionando una coppia da ciascuna lista e ottenere un prodotto di 2w primi, se abbiamo w le liste.La domanda finale è quello che fa questo prodotto raccontarci le coppie abbiamo selezionato e moltiplicato?Se le coppie di forma di una selezione valida, non abbiamo mai scegliere un simbolo per due volte, quindi il prodotto non contiene prime due piazza libero.Se la selezione non è valido il prodotto contiene almeno il doppio e non è quadrato libero.E qui un esempio finale.

X((2, 5)) = 5 * 13 = 65
X((3, 6)) = 7 * 17 = 119
X((3, 4)) = 7 * 11 = 77

La selezione 25 e 36 i rendimenti 65 * 119 = 7735 = 5 * 7 * 13 * 17 ed è quadrato libero, quindi valido.La selezione 36 e 34 i rendimenti 119 * 77 = 9163 = 7² * 11 * 17 e non è quadrato libero, quindi non valido.

Anche nota come bene questo conserva l'symmetrie - X (m, n)) = X((n, m)) - e prohibites simmetrica coppie perché X((m, m)) = M(m) * M(m) non è quadrato libero.

Non so se questo sarà di aiuto, ma ora lo sapete e potete pensare...^^

Questa è la prima parte di una riduzione di 3-SAT problema a questo problema.3-IMPOSTARE problema è il seguente.

(!A | B | C) & (B | !C | !D) & (A | !B)

E qui è la riduzione, per quanto ho ottenuto.

m-n rappresenta una coppia
una linea reprresents un elenco
un asterisco rappresenta un unico simbolo arbitrario di una

A1-A1'    !A1-!A1'     => Select A true or false
B1-B1'    !B1-!B1'     => Select B true or false
C1-C1'    !C1-!C1'     => Select C true or false
D1-D1'    !D1-!D1'     => Select D true or false

A1-*   !B1-*   !C1-*   => !A | B | C

A2-!A1'   !A2-A1'      => Create a copy of A
B2-!B1'   !B2-B1'      => Create a copy of B
C2-!C1'   !C2-C1'      => Create a copy of C
D2-!D1'   !D2-D1'      => Create a copy of D

!B2-*  C2-*    D2-*    => B | !C | !D

(How to perform a second copy of the four variables???)

!A3-*  B3-*

Se io (o qualcun altro) può completare questa riduzione e mostrano come farlo nel caso generale, questa sarà la prova che il problema NP-completo.Io sono appena bloccato con la copia variabili a seconda del tempo.

che sto per dire che non c'è nessun calcolo che si può fare altro che la forza bruta becuse v'è una funzione che deve essere valutata per decidere se un elemento dal set B può essere utilizzato dato l'articolo scelto in serie A. Semplice combinatoria lavoro matematica abituato.

È possibile velocizzare il calcolo da 1 a 2 magnitudini utilizzando Memoizzazione e hashing.

Memoizzazione è ricordare i risultati precedenti di simili percorsi di forza bruta. Se siete a lista n e si è già consumato simboli x, y, z e in precedenza si è incontrato questa situazione, allora verrà aggiunto nello stesso numero di combinazioni possibili dalle altre liste. Non importa come Hai avuto modo di elencare n utilizzando x, y, z. Quindi, utilizzare un risultato in cache se ce n'è uno, o continuare il calc alla lista successiva e controllare lì. Se si effettua una forza bruta algoritmo ricorsivo per calcolare il risultato, ma i risultati della cache, questo funziona alla grande.

La chiave per il risultato salvato è: l'elenco corrente, ei simboli che sono stati utilizzati. Ordinare i simboli per rendere la vostra chiave. Penso che un dizionario o un array di dizionari ha un senso qui.

Usa hashing per ridurre il numero di coppie che devono essere ricercate in ogni lista. Per ciascuna lista, fare un hash delle coppie che sarebbero disponibili dato che un certo numero di simboli sono già consumati. Scegliere il numero di simboli consumati che si desidera utilizzare nel vostro hash basato sulla quantità di memoria che si desidera utilizzare e il tempo che si desidera trascorrere pre-calcolo. Credo che con 1-2 simboli sarebbe buono. Ordina questi hash per il numero di elementi in loro ... ascendenti, e poi tenere la parte superiore n. Dico buttare via il resto, lo stavano ristrutturando se l'hash riduce solo il tuo lavoro una piccola quantità, la sua probabilmente non vale la pena tenere (ci vorrà più tempo per trovare l'hash se ci sono più di loro). Quindi, come si passa attraverso le liste, si può fare una scansione rapida hash della lista per vedere se si è utilizzato un simbolo nel hash. Se avete, quindi utilizzare il primo hash che si avvicina a scorrere la lista. Il primo hash conterrebbe le coppie minor numero di eseguire la scansione. Se siete veramente a portata di mano, si potrebbe essere in grado di costruire questi hash, come si va e non perdere tempo in anticipo per farlo.

Si potrebbe essere in grado di lanciare l'hash e utilizzare un albero, ma la mia ipotesi è che la compilazione l'albero ci vorrà molto tempo.

programmazione a vincoli è un approccio bello se si desidera generare tutte le combinazioni. Giusto per provare, ho scritto un modello utilizzando Gecode (versione 3.2.2) per risolvere il problema. I due esempi riportati sono molto facili da risolvere, ma altri casi potrebbe essere più difficile. Dovrebbe essere migliore di generare e di prova, in ogni caso.

/*
 *  Main authors:
 *     Mikael Zayenz Lagerkvist <lagerkvist@gecode.org>
 *
 *  Copyright:
 *     Mikael Zayenz Lagerkvist, 2009
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */
#include <gecode/driver.hh>
#include <gecode/int.hh>
#include <gecode/minimodel.hh>

using namespace Gecode;

namespace {
  /// List of specifications
  extern const int* specs[];
  /// Number of specifications
  extern const unsigned int n_specs;
}


/**
 * \brief Selecting pairs
 *
 * Given a set of lists of pairs of values, select a pair from each
 * list so that no value is selected more than once.
 *
 */
class SelectPairs : public Script {
protected:
  /// Specification
  const int* spec;
  /// The values from all selected pairs
  IntVarArray s;
public:
  /// The actual problem
  SelectPairs(const SizeOptions& opt)
    : spec(specs[opt.size()]),
      s(*this,spec[0] * 2,Int::Limits::min, Int::Limits::max) {

    int pos = 1; // Position read from spec
    // For all lists
    for (int i = 0; i < spec[0]; ++i) {
      int npairs = spec[pos++];
      // Construct TupleSet for pairs from list i
      TupleSet ts;
      for (int p = 0; p < npairs; ++p) {
        IntArgs tuple(2);
        tuple[0] = spec[pos++];
        tuple[1] = spec[pos++];
        ts.add(tuple);
      }
      ts.finalize();

      // <s[2i],s[2i+1]> must be from list i
      IntVarArgs pair(2);
      pair[0] = s[2*i]; pair[1] = s[2*i + 1];
      extensional(*this, pair, ts);
    }

    // All values must be pairwise distinct
    distinct(*this, s, opt.icl());

    // Select values for the variables
    branch(*this, s, INT_VAR_SIZE_MIN, INT_VAL_MIN);
  }

  /// Constructor for cloning \a s
  SelectPairs(bool share, SelectPairs& sp) 
    : Script(share,sp), spec(sp.spec) {
    s.update(*this, share, sp.s);
  }

  /// Perform copying during cloning
  virtual Space*
  copy(bool share) {
    return new SelectPairs(share,*this);
  }

  /// Print solution
  virtual void
  print(std::ostream& os) const {
    os << "\t";
    for (int i = 0; i < spec[0]; ++i) {
      os << "(" << s[2*i] << "," << s[2*i+1] << ") ";
      if ((i+1) % 10 == 0)
        os << std::endl << "\t";
    }
    if (spec[0] % 10)
      os << std::endl;
  }
};

/** \brief Main-function
 *  \relates SelectPairs
 */
int
main(int argc, char* argv[]) {
  SizeOptions opt("SelectPairs");
  opt.iterations(500);
  opt.size(0);
  opt.parse(argc,argv);
  if (opt.size() >= n_specs) {
    std::cerr << "Error: size must be between 0 and "
              << n_specs-1 << std::endl;
    return 1;
  }
  Script::run<SelectPairs,DFS,SizeOptions>(opt);
  return 0;
}

namespace {
  const int s0[] = {
    // Number of lists
    3,
    // Lists (number of pairs, pair0, pair1, ...)
    5,  1,2,  1,3,  1,4,  2,3,  2,4,
    3,  1,4,  1,5,  2,5,
    5,  1,6,  1,7,  2,5,  2,6,  3,6
  };

  const int s1[] = {
    // Number of lists
    3,
    // Lists (number of pairs, pair0, pair1, ...)
    5,  1,2,  2,3,  3,4,  4,5,  6,7,
    5,  1,2,  2,3,  3,4,  4,5,  6,7,
    5,  1,2,  2,3,  3,4,  4,5,  6,7
  };

  const int *specs[] = {s0, s1};
  const unsigned n_specs = sizeof(specs)/sizeof(int*);
}

Prima prova .. Ecco un algoritmo con una migliore riduzione media complessità che la forza bruta. In sostanza si crea stringhe con crescente lunghezze in ogni iterazione. Questo potrebbe non essere la soluzione migliore, ma ci attenderà il migliore da trovare ...:)

Inizia con l'elenco 1. Tutte le voci in tale elenco sono soluzioni valide di lunghezza 2 (# = 5) Successivamente, quando si introduce lista 2. tenere un registro di tutte le soluzioni valide di lunghezza 4, che finiscono per essere {1425, 2314, 2315, 2415} (# = 4).

Quando si aggiunge la terza lista per il mix, ripetere il processo. Vi ritroverete con {142536, 241.536} (# = 2).

La riduzione della complessità viene in luogo, perché si sta gettando via cattive stringhe in ogni iterazione. Il caso peggiore sembra essere sempre lo stesso -. Nel caso in cui tutte le coppie sono distinti

Questo si sente come un buon problema a cui applicare un approccio di programmazione . Per la lista dei pacchetti forniti da Wikipedia io aggiungere che ho avuto una buona esperienza con Gecode in passato ; gli esempi Gecode forniscono anche un tutorial di base a vincolo di programmazione. vincolo Processing è un buon libro sul tema, se si vuole scavare più in profondità come gli algoritmi di lavoro.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow