Как объединить два генератора нетривиальным способом

Это довольно просто в Хаскелле:

merge as bs =
  case (as, bs) of
    ([], _) -> bs
    (_, []) -> as
    ((a:as'), (b:bs')) ->
      if a <= b
        then a : (merge as' bs)
        else b : (merge as bs')
rmDups as =
  case as of
    [] -> []
    [a] -> [a]
    (a:bs@(b:_)) ->
      if a == b
        then rmDups bs
        else a:(rmDups bs)
take 25 $ rmDups $ merge (map (2^) [1..]) (map (3^) [1..])

дает следующее:

[2,3,4,8,9,16,27,32,64,81,128,243,256,512,729,1024,2048,2187,4096,6561,8192,16384,19683,32768,59049]

хотя я представляю, что есть более элегантный способ сделать это...

] Просто объедините два заказанных списка []a la[] [

(define merge
  (lambda (pred ls1 ls2)
    (cond
      [(null? ls1) ls2]
      [(null? ls2) ls1]
      [(pred (car ls1) (car ls2))
       (cons (car ls1) (merge pred (cdr ls1) ls2))]
      [else (cons (car ls2) (merge pred ls1 (cdr ls2)))])))

], поднятых из [] здесь [].[

] Простое решение для любого примера - это создание нового.[

for (i = 0; i < X; i++)
{
 if (i%2 or i%3)
 {
  cout << i
 }
}

]edit: X - это сколько времени вы хотите запустить его, скажем, вы хотите вывести 0-100 put 100.[

int counter = 1000;
bool done = false;
while(!done)
{
 if (i%2 or i%3)
 {
  cout << i;
  counter--;
  if(counter <= 1)
   {
     done = true;
   }
 }
i++;
}

]Это немного запутанно, но должно работать.[

]edit: Счетчик должен заканчиваться на 1, или он даст вам 1001 элемент.[

]По крайней мере, если я понимаю ваш вопрос, вам нужно просто объединить результаты от двух генераторов:[

][
1. ]Генерировать выход от каждого генератора[
] [
2. ]Генерировать меньшее из двух в качестве следующего выхода[
] [
3. ]Генерировать следующий выход от этого генератора[
] [
4. ]Вернуться к Шагу 2[
][

]Если два генератора производят равные значения, генерировать их в качестве выхода, и генерировать следующее значение от каждого генератора. [

]Обратите внимание, что хотя он обычно используется для сортировки существующих данных вместо генерации новых, это похоже на слияние, используемое в обычной сортировке слияния, за исключением того, что я предположил, что вам не нужны дубликаты, где в сортировке слияния обычно сохраняются дубликаты. [

]Правка: Благодаря lpthnc я перечитал вопрос, и думаю, что он прав - я неправильно понял исходный вопрос. Чтобы получить правильный вывод, нужно создать третий генератор и произвести кратные числа (в данном случае) шести, а также использовать трехходовое слияние между этим результирующим множеством и двумя другими генераторами.[

]Я не очень-то много с ним играл, но я считаю, что уровень языка Lazy (или ленивый модуль) в последних итерациях PLT Scheme позволил бы вам написать код для генерации всей бесконечной последовательности, которая теоретически использовала бы бесконечное время и память, но оценивала бы только конечное подмножество этого по мере необходимости.[

]Redacted. Чем больше я смотрю на это, тем больше мне кажется, что я всё неправильно понял - и у других, похоже, уже есть ответы получше.[

][] Извините, ничего этого нет в схеме, только псевдокод...[][

]Следующий код соответствует мыслительному процессу, который я получил из вашего вопроса:[

]EDIT: переработал псевдокод, теперь, когда я понял, что это "2^i*3^j", а не "2^i, 3^j"[

 // If i got close, this time,
 // inputs min-i=0, max-i=2, min-j=0, max-j=2
 // should get output like
 //  2^0 * 3^0 = 1
 //  2^0 * 3^1 = 3
 //  2^0 * 3^2 = 6
 //  2^1 * 3^0 = 2
 //  2^1 * 3^1 = 6
 //  2^1 * 3^2 = 12
 //  2^2 * 3^0 = 4
 //  2^2 * 3^1 = 12
 //  2^2 * 3^2 = 24

 LET min-i, max-i, min-j, max-j be input
 LET current-value = 1

 FOR i = min-i to max-i
   FOR j = min-j to max-j DO
     PRINT "2^" . i . " * j^" . j . " = " . current-value
     current-value *= 3;
   DONE // end j loop

   current-value *= 2
 DONE // end i loop

][

Я не очень разбираюсь в генераторах, однако я могу предложить решение, основанное на потоках (лениво построенных, возможно бесконечные списки), которые в чем-то похожи.

Мой подход - создать поток чье «состояние» само было бы потоком потоков.

Индивидуальные внутренние потоки чисел, назовем их 3-потоками, будет представлять списки последовательных степеней 3, начиная с 1, умноженное на заданную степень двойки. Затем мы можем собрать бесконечное количество таких 3-потоков, по одному на каждую последовательную степень двойки, начиная с 1. Назовем это двухпотоковым.

Начальное состояние в ascii-art следующее:

---------------------- --- -- -
| The 2-stream ...
--|----|----|----|---- --- -- -
  V    V    V    V
 |1| | 2| | 4| | 8|
 |3| | 6| |12| |24| ...
 |9| |18| |36| |72|         The 3-streams
  :    :    :    :

Теперь мы собираемся манипулировать этим так, чтобы в любой момент 3 потока будут упорядочены внутри 2 потока Что касается их первых элементов. Как следствие, следующее наименьшее сгенерированное число всегда будет первым элементом первого 3-потока.

Итак, чтобы получить следующее число в последовательности, которую вы хотите получить, мы собираемся вытащить первые 3 потока, вытащите его первый элемент (это число, которое нас интересует), а затем повторно вставьте 3-поток в 2-поток в позиции, определяемой его новым первым элементом. Новое состояние после извлечения первого числа (1) будет следующим:

---------------------- --- -- -
| The 2-stream ...
---|----|----|----|---- --- -- -
   V    V    V    V
 | 2| | 3| | 4| | 8|
 | 6| | 9| |12| |24| ...
 |18| |27| |36| |72|         The 3-streams
  :    :    :    :

Обратите внимание, что этот метод не зависит конкретно от 2 ^ i, 3 ​​^ j или умножения. (только на 2 ^ i * 3 ^ j, монотонно возрастающем с i и j). Я опубликовал еще один ответ, и в результате намного проще и быстрее . не верьте мне: это не имеет ничего общего с математикой

Ниже приведен пример реализации с использованием потоков SRFI-41 :

(require srfi/41)

; Geometric sequence with initial value 'init', and ratio 'r'
(define (make-geoseq init r)
  (stream-cons
    init
    (make-geoseq (* r init) r)))

; Your power generators
(define pow2 (make-geoseq 1 2))
(define pow3 (make-geoseq 1 3))

; Construct a 3-stream from the pow3 sequence
(define (make-3stream mult)
  (stream-map (lambda (x) (* mult x)) pow3))

; Construct the (initial) 2-stream from the pow2 sequence
(define initial-2stream
  (stream-map make-3stream pow2))

; Insert a modified 3-stream into the given 2-stream, at the right position
(define (insert two-stream three-stream)
  (if (< (stream-car three-stream)
         (stream-car (stream-car two-stream)))
    ; we have the smallest 3-stream, put it at the front
    (stream-cons
      three-stream
      two-stream) 
    ; otherwise, recurse
    (stream-cons
      (stream-car two-stream)
      (insert (stream-cdr two-stream) three-stream))))

; Construct a 2^n * 3^p stream with the given 2-stream as its "state"
(define (make-the-stream current-2stream)
  (let*
    ; pull out the first 3-stream
    ((first-3s (stream-car current-2stream))
     (other-3s (stream-cdr current-2stream))
     ; use its first element as our next value
     (next-val (stream-car first-3s))
     ; reinsert its tail into the 2-stream's tail
     (next-2s (insert other-3s (stream-cdr first-3s))))

    ; and use the resulting 2-stream to construct the (outer) stream's tail
    (stream-cons
      next-val
      (make-the-stream next-2s))))

; Now, we can construct the stream we want
(define the-stream (make-the-stream initial-2stream))

Использование схемы plt (на моем довольно дрянном аппаратное обеспечение):

$ mzscheme -f pow23.scm -e '(display (stream->list (stream-take 20 the-stream)))'
(1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 64 72 81 96)

$ time mzscheme -f pow23.scm -e '(display (stream-ref the-stream 10000))'
161968247347450370721577384417107686788864605658546176
real    0m12.550s
user    0m11.005s
sys     0m0.340s

Я думаю, реализовать это с помощью генераторов можно, но сложнее всего будет реализовать (вставить) . Вы можете сделать это, составив генераторы, но вы в конечном итоге добавляете один "слой" каждый раз, когда вытаскивают число, тогда как поток, созданный с помощью (вставить) , разделяет свой хвост с исходным («слои» со временем сливаются).