Generowanie liczb rosnąco za pomocą mnozenia ich zbioru między sobą

Witam,
Mam pewien problem odnośnie stworzenia pewnego rozwiązania.
Mianowice posiadam zbiór jakiś K elementów X, i chcę wygenerować rosnący ciąg liczb (o długości N) które będą wygenerowane za pomocą mnozenia tych liczb między sobą.

Np.
X = {1, 2,3,5}

dla N = 9
Ciag: 1, 2, 3, 4, 5, 6, 8, 9, 10

Utknąłem w punkcie: W jaki sposób można wygenerować te liczby rosnąco?

Za każdą wskazówkę serdecznie dziękuję.

Edit: Był błąd, N miało być równe w przykładzie 9 nie 10

1. Wygenerować listę w dwóch pętlach
2. Posortować
3. Usunąć duplikaty

Wydaje sie ze zakladajac ze wejscie jest posortowane mozesz to zrobic liniowo zachlannie. Pamietajac ze wyjscie jest tez jednym z wejsc.

Zrozumiałem pytanie za trzecim czytanie. Ty chcesz wyliczyć wszystkie liczby które rozkładają się na liczby z podanego zbioru, można używac dzielnika wielokrotnie

KamilAdam napisał(a):

Zrozumiałem pytanie za trzecim czytanie. Ty chcesz wyliczyć wszystkie liczby które rozkładają się na liczby z podanego zbioru, można używac dzielnika wielokrotnie

Faktycznie. Więc w najprostszym rozwiązaniu wystarczy pętla od i = K[0] i sprawdzać czy którykolwiek element tablicy daje resztę z dzielenia 0 lub K[i] == i. Skończyć po N trafieniach.

Możesz bardziej opisać w jaki sposób to zrobić?

Nie umiem w C++, ale w pseudokodzie byłoby to tak:

def checkNumber(divisors: List[Int])(k : Int): Boolean = divisors match {
  case Nil    => k == 1
  case h :: t => if (k % h == 0) checkNumber(divisors)(k/h) else checkNumber(t)(k)
}

val x = List(2, 3, 4, 5)
val result = LazyList.from(2).filter(checkNumber(x)).take(9).toList

println(result)

Uwaga: Nie działa dla 1 w dzielnikach. Ogólnie sprowadza się to do napisania funkcji checkNumber która sprawdza czy liczba k dzieli się przez dzielniki. Jak liczba k nie dzieli się już przez dzielnik to biorę kolejny z listy dzielników. Jak skończą się dzielniki to jeśli doszedłem do 1 to się udało. Jak jest coś innego to się nie udało i liczbę należy odrzucić (zwrócić false)

Tylko że dostaję N czyli ile tych liczb mamy wygenerować a nie do jakiej liczby N mam wygenerować. Więc dzielenie N przez dzielniki nie ma sensu.

eh, eh, eh. Zmienię moje małe n na k ja sprawia ci to problemy ze zrozumieniem. Moje małe n nie ma nic wspólnego z twoim dużym N

To ile chcesz liczb takich jest już zupełnie innym problemem. Moja funkcja checkNumber sprawdza czy liczba k rozkłada się na dzielniki z listy

nie znam c++ ale to działa

int K[] = { 1, 2, 3, 5 };
int N = 9;

for (int i = K[0]; N; i ++) {
  int dividend = i;
  int divisors = 0;
  for (int j = 0; j < sizeof(K) / sizeof(K[0]); j ++) {
    int divisor = K[j];
    if (divisor != 0 && divisor != 1)
      while (dividend > divisor && dividend % divisor == 0) {
        dividend /= divisor;
        divisors ++;
      }
    
    if (dividend == divisor && (divisors || divisor == 1)) {
      cout << i << " ";
      N --;
      break;
    }
  }
}

Wersja C++ nie dziala np. dla:

int K[] = { 5 };
int N = 1;

W wyniku jest 5, ktore nie jest uzyskane za "pomocą mnozenia tych liczb między sobą". Z opisu mi wynika ze na wyjsciu powinno byc 25.

Z ciekawosci sprawdzilem czy wersja w scali jest w stanie sie policzyc. Dla

val x = List(32767)
val result = LazyList.from(2).filter(checkNumber(x)).take(2).toList

nie doczekalem sie

@Mondonno - wydaje mi sie ze to co wczesniej napisalem jest wystarczajaca podpowiedzia. Zeby uproscic implementacje proponuje zaczac od wersji bez "Pamietajac ze wyjscie jest tez jednym z wejsc." (oczywiscie wtedy zniknie 8 z przykladu ktory podales)

Po głebokim przeszukaniu różnych źródeł udało mi sie stworzyć kod który rozwiązuje ten problem w O(n*K)

n - ilość liczb do wygenerowania
K - ilość składników tablicy X

#include <iostream>
#include <algorithm>
#include <vector>
   
using namespace std;

vector<long long> solve(long long n, vector<long long> to_create_from) {
    vector<long long> primes = to_create_from;
    vector<long long> values = to_create_from;
            
    vector<long long> indexes(to_create_from.size());
    vector<long long> results(n);
            
    for (long long iter = 1; iter < n; iter++) {
        results[iter] = values[0];
        for (long long p = 1; p < primes.size(); p++)
            if (results[iter] > values[p])
                results[iter] = values[p];

        for (long long p = 0; p < primes.size(); p++)
            if (results[iter] == values[p])
                values[p] = primes[p] * results[++indexes[p]];
    }

    return results;
}
   
int main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);

   long long N, K;
   cin >> N >> K;

   vector<long long> X(K);
   for(int i = 0; i < K; i++) {
       cin >> X[i];
   }

   vector<long long> results = solve(N, X);
   for(auto value : results) cout << value << " ";
   cout << "\n";
}

Pomysł polega na tym aby brać minimum, dodawać te minimum do tablicy podnosić minimum do następnej wartości i tak dalej.
Wrzuciłem ten pomysł (z pomocą wielu źródeł) z myślą żeby inni też mogli z niego skorzystać.

Mondonno napisał(a):

Wrzuciłem ten pomysł (z pomocą wielu źródeł) z myślą żeby inni też mogli z niego skorzystać.

Pośpieszyłeś się, nie działa poprawnie, przykład wejścia: N K K0 K1 K2 ...
3 4 1 2 10000 10001 wynik 0 1 1

@Mondonno twój kod nie działa nawet dla najprostszych przypadków (pada nawet na przykładzie z pytania):
https://godbolt.org/z/3vsc4dvh7

Elementy wrzucaj do std::set<long> on Ci zapewni, że żaden element się nie powtórzy i wszystko będzie posortowane.

Wikipedia: Smooth number