Come modellare una combinazione infinita non lineare? [chiuso]

-3

Sia L un insieme ordinato di numeri interi positivi (ad esempio, l'insieme di tutti i numeri primi).

Qui, #L = infinito, e N è un numero positivo che serve come limite superiore. L'obiettivo è elencare il seguente set M:

M = {all combinazioni non lineari moltiplicative di L | ogni combinazione moltiplicativa < N}

Ad esempio, se L = {a,b,c, ..., inf} , uno snippet di combinazione potrebbe essere

{a*b   ,a*c    ,...,   a*inf}
{a^2 *b, a^2 *c,..., a^2*inf}
...
{a*b*c , a*c*d ,..., y*z*inf}
...

Supponendo che L sarebbe finito, con #L = n, allora il programma richiederebbe n livelli di looping, ma nel mio problema n è sconosciuto, invece c'è la condizione su N. Non so come loop un numero sconosciuto di livelli nidificati . È questo, ma con cui sono alle prese: come modellare un numero sconosciuto di loop, piuttosto che una soglia sconosciuta.

Dettagli specifici del problema

Elenco : elenco dei numeri primi P che si sta espandendo.

Vincoli : non-primi (nessuna combinazione moltiplicatrice lineare di numeri primi) sotto N.

    
posta Error 05.11.2017 - 22:32
fonte

2 risposte

2

Non sono proprio sicuro di aver capito cosa stai cercando, ma quello che mi hai chiesto mi sembra che possa essere risolto in questo modo (che richiede 3 cicli annidati, non di più):

  1. inizia con L1 = {a}, genera tutte le "combinazioni non lineari moltiplicative" contenenti a (quindi a ^ 2, a ^ 3, ...) sotto N. Consente di chiamare questi prodotti P1, è un insieme finito .
  2. continua con L2 = {a, b}, genera tutte queste combinazioni dove b è un fattore (a ^ 2 * b, a ^ 3 * b, a ^ 4 * b, ...), (a ^ 2 * b ^ 2, a ^ 3 * b ^ 2, ...), dove nessun numero supera N. È possibile utilizzare i risultati del passaggio 1 e implementarlo in questo modo:

     P0={1}
     Q=union of P0,P1
     for(i=1; b^i < N; ++i):
        for each p in Q:
           if b^i*p > N: break;
           P2.insert(b^i*p);
    
  3. ora vedi come continua: diciamo L3 = {a, b, c}, genera tutte le combinazioni dove c è un fattore. Fai questo utilizzando il set di risultati P2:

     Q=union of P0,P1,P2
     for(i=1; c^i < N; ++i):
        for each p in Q:
           if c^i*p > N: break;
           P3.insert(c^i*p);
    

Ripeti fino all'ultimo elemento del passaggio k, l'ultimo elemento di L_k supera N (in realtà N / 2 dovrebbe essere sufficiente).

Infine, unisci i risultati P1, P2, ..., P_k in un unico set di risultati.

    
risposta data 06.11.2017 - 21:28
fonte
3

Molte lingue supportano serie infinite con stream pigri valutati . È possibile operare sugli stream senza effettivamente valutare alcun elemento nel flusso. Qui è un esempio di Scala per la sequenza di Fibonacci.

Ecco un esempio di Scala che produce combinazioni

val L = "abcdefghijklmnopqrstuvwxyz".toCharArray.toList.map(_.toString).toStream
def combinations(stream: Stream[String], i: Int): Stream[Stream[String]] =
    stream.combinations(i).toStream.map(comb => 
        comb.reduceLeft((a, b) => s"$a*$b")) #:: combinations(stream, i + 1)
val N = 4
val result = combinations(L.take(N), 1).take(N)
result.toList.foreach(s => println(s.toList))

I rendimenti

List(a, b, c, d)
List(a*b, a*c, a*d, b*c, b*d, c*d)
List(a*b*c, a*b*d, a*c*d, b*c*d)
List(a*b*c*d)
    
risposta data 06.11.2017 - 01:22
fonte