使用一组素数按升序排列生成整数 [英] Generating integers in ascending order using a set of prime numbers

问题描述

我有一组素数的和我只用那些主要因素在增加，以生成一个整数。

I have a set of prime numbers and I have to generate integers using only those prime factors in increasing order.

例如，如果设定的是的 P = {2,5}，则我的整数应为1，2，4，5，8，10，16，20，25，...

For example, if the set is p = {2, 5} then my integers should be 1, 2, 4, 5, 8, 10, 16, 20, 25, …

有没有什么有效的算法来解决这个问题？

Is there any efficient algorithm to solve this problem?

推荐答案

其基本思想是，1为集的成员，并为设置的 N 的每个成员也是如此2 N 的和5的 N 的是一组的成员。这样，你就开始通过输出1，推动2和5到优先级队列。然后，反复弹出优先队列的前面项，输出它，如果它是从previous输出不同，并推2倍和5倍的数量到优先级队列。

The basic idea is that 1 is a member of the set, and for each member of the set n so also 2n and 5n are members of the set. Thus, you begin by outputting 1, and push 2 and 5 onto a priority queue. Then, you repeatedly pop the front item of the priority queue, output it if it is different from the previous output, and push 2 times and 5 times the number onto the priority queue.

谷歌海明号或普通号码，或转至 A003592 ，以了解更多信息。

Google for "Hamming number" or "regular number" or go to A003592 to learn more.

-----后来加入-----

----- ADDED LATER -----

我决定把钱花在我的午餐时间几分钟就可以编写一个程序来实现上述算法，用Scheme编程语言。首先，这里是库实现使用配对堆算法优先级队列：

I decided to spend a few minutes on my lunch hour to write a program to implement the algorithm described above, using the Scheme programming language. First, here is a library implementation of priority queues using the pairing heap algorithm:

(define pq-empty '())
(define pq-empty? null?)

(define (pq-first pq)
  (if (null? pq)
      (error 'pq-first "can't extract minimum from null queue")
      (car pq)))

(define (pq-merge lt? p1 p2)
  (cond ((null? p1) p2)
        ((null? p2) p1)
        ((lt? (car p2) (car p1))
          (cons (car p2) (cons p1 (cdr p2))))
        (else (cons (car p1) (cons p2 (cdr p1))))))

(define (pq-insert lt? x pq)
  (pq-merge lt? (list x) pq))

(define (pq-merge-pairs lt? ps)
  (cond ((null? ps) '())
        ((null? (cdr ps)) (car ps))
        (else (pq-merge lt? (pq-merge lt? (car ps) (cadr ps))
                            (pq-merge-pairs lt? (cddr ps))))))

(define (pq-rest lt? pq)
  (if (null? pq)
      (error 'pq-rest "can't delete minimum from null queue")
      (pq-merge-pairs lt? (cdr pq))))

现在的算法。功能 F 有两个参数，该号码的列表中设置的 PS 的和数字的 n项输出的的从输出的头部。该算法略有改变;优先级队列由推动1初始化，则提取步骤开始。可变的 P 的是previous产值（最初为0）， PQ 的是优先级队列， XS 的是输出列表，该列表蓄积在相反的顺序。这里的code：

Now for the algorithm. Function f takes two parameters, a list of the numbers in the set ps and the number n of items to output from the head of the output. The algorithm is slightly changed; the priority queue is initialized by pushing 1, then the extraction steps start. Variable p is the previous output value (initially 0), pq is the priority queue, and xs is the output list, which is accumulated in reverse order. Here's the code:

(define (f ps n)
  (let loop ((n n) (p 0) (pq (pq-insert < 1 pq-empty)) (xs (list)))
    (cond ((zero? n) (reverse xs))
          ((= (pq-first pq) p) (loop n p (pq-rest < pq) xs))
          (else (loop (- n 1) (pq-first pq) (update < pq ps)
                      (cons (pq-first pq) xs))))))

对于那些不熟悉的方案，循环是一个递归调用本地定义的函数， COND 是的if-else链的头;在这种情况下，有三个 COND 子句，具有predicate和随之而来的各条款，与评价的量，predicate是第一子句随之而来真正。在predicate （零？N）终止递归和返回输出列表按正确的顺序。在predicate （=（PQ-第一PQ）P）表示优先级队列的现任掌门人已经输出previously，因此它被忽略重复与优先队列的第一个项目之后的其余部分。最后，其他 predicate，这始终是真实的，确定一个新的号码将被输出，所以它递减计数器，节约优先级队列的当前头新的previous值，更新优先级队列添加当前数量的新的儿童，并插入优先级队列的现任掌门成积聚输出。

For those not familiar with Scheme, loop is a locally-defined function that is called recursively, and cond is the head of an if-else chain; in this case, there are three cond clauses, each clause with a predicate and consequent, with the consequent evaluated for the first clause for which the predicate is true. The predicate (zero? n) terminates the recursion and returns the output list in the proper order. The predicate (= (pq-first pq) p) indicates that the current head of the priority queue has been output previously, so it is skipped by recurring with the rest of the priority queue after the first item. Finally, the else predicate, which is always true, identifies a new number to be output, so it decrements the counter, saves the current head of the priority queue as the new previous value, updates the priority queue to add the new children of the current number, and inserts the current head of the priority queue into the accumulating output.

既然是不平凡的，以更新该优先级队列来添加的当前数量的新的儿童，该操作被提取到一个单独的功能：

Since it is non-trivial to update the priority queue to add the new children of the current number, that operation is extracted to a separate function:

(define (update lt? pq ps)
  (let loop ((ps ps) (pq pq))
    (if (null? ps) (pq-rest lt? pq)
      (loop (cdr ps) (pq-insert lt? (* (pq-first pq) (car ps)) pq)))))

函数循环通过 PS 集合中的元素，每个插入依次优先级队列;在如果返回更新后的优先级队列，减去其老脸，当 PS 列表已用尽。该递归步骤剥离 PS 列表的头 CDR 并插入优先级队列头部的产物，在 PS 列表的头到优先级队列。

The function loops over the elements of the ps set, inserting each into the priority queue in turn; the if returns the updated priority queue, minus its old head, when the ps list is exhausted. The recursive step strips the head of the ps list with cdr and inserts the product of the head of the priority queue and the head of the ps list into the priority queue.

下面是该算法的两个例子：

Here are two examples of the algorithm:

> (f '(2 5) 20)
(1 2 4 5 8 10 16 20 25 32 40 50 64 80 100 125 128 160 200 250)
> (f '(2 3 5) 20)
(1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36)

您可以运行的程序在 http://ideone.com/sA1nn 。

这篇关于使用一组素数按升序排列生成整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！