Супер уродливый номер

Итак, проблема в следующем:

Напишите программу для нахождения n-го суперуродливого числа.

Сверхуродливые числа — это положительные числа, все простые делители которых входят в заданный список простых чисел размера k. Например, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] — это последовательность первых 12 суперуродливых чисел с заданными простыми числами = [2, 7, 13, 19]. размера 4.

Таким образом, мой алгоритм в основном находит все возможные факторы, используя шаблон, которому они следуют, помещает их в массив, сортирует этот массив и затем возвращает n-е значение в массиве. Он точно вычисляет их все, однако слишком медленно работает с большими значениями n.

Мой вопрос в том, как правильно это сделать, поскольку я уверен, что должно быть более простое решение. Меня больше всего интересует теория, стоящая за его поиском, и есть ли для этого какая-то закрытая формула.

 var nthSuperUglyNumber = function(n, primes) {
     xprimes = primes;
     var uglies = [1];
     uglies = getUglyNumbers(n, primes, uglies);
     // return uglies[n-1];
     return uglies[n - 1];
 };

 //                     3                         4
 //1, 2,3,5, || 4,6,10, 9,15, 25, || 8,12,20,18,30,50, 27,45,75, 125 ||
 //   3,2,1     6,3,1,               10,4,1
 //              1            1              1
 //1, 2,3 || 4,6, 9, || 8,12,18, 27 || 16,24,36,54, 81
 //   2,1    3,1        4,1            5,1
 //
 //1, 2,3,5,7 || 4,6,10,14 9,15,21 25,35, 49 ||
 //   4,3,2,1 || 10,6,3,1

 var getUglyNumbers = function(n, primes, uglies) {
     if (n == 1) {
         return uglies;
     }
     var incrFactor = [];

     var j = 0;
     // Initial factor and uglies setup
     for (; j < primes.length; j += 1) {
         incrFactor[j] = primes.length - j;
         uglies.push(primes[j]);
     }

     //recrusive algo
     uglies = calcUglies(n, uglies, incrFactor);
     uglies.sort(function(a, b) {
     return a - b;
     });
     return uglies;
 };

 var calcUglies = function(n, uglies, incrFactor) {
     if (uglies.length >= 5 * n) return uglies;
     var currlength = uglies.length;
     var j = 0;
     for (j = 0; j < xprimes.length; j += 1) {
         var i = 0;
         var start = currlength - incrFactor[j];
         for (i = start; i < currlength; i += 1) {
             uglies.push(xprimes[j] * uglies[i]);
         }
     }
     // Upgrades the factors to level 2
     for (j = 1; j < xprimes.length; j += 1) {
         incrFactor[xprimes.length - 1 - j] = incrFactor[xprimes.length - j] + incrFactor[xprimes.length - 1 - j];
     }

     return calcUglies(n, uglies, incrFactor);
 };

optimization performance primes prime-factoring smooth-numbers
person yehyaawad    schedule 05.12.2015    source источник
comment
каков размер k и насколько высоки высокие n-е значения?   -  person bolov    schedule 08.12.2015
comment
Я думаю, что задача NP-полная. Алгоритмы не моя сильная сторона, поэтому могу ошибаться.   -  person bolov    schedule 08.12.2015
comment
после уточняющего редактирования (спасибо, @WernerHenze!) это тесно связано с stackoverflow.com/questions/10126285/ (я ссылаюсь на свой ответ вместо самого вопроса, потому что я думаю, что это лучше, чем принятый ответ) и stackoverflow.com/questions/9242733/. формула оценки величины n-го числа из Википедии должна быть как-то скорректирована.   -  person Will Ness    schedule 08.12.2015
comment
@bolov это определенно НЕ NP-полный, потому что у него нет ответа Да / Нет.   -  person gnasher729    schedule 13.07.2020

Ответы (4)


arrow_upward
2
arrow_downward 

public static ArrayList<Integer> superUgly(int[] primes,int size)
{
    Arrays.sort(primes);
    int pLen = primes.length;

    ArrayList<Integer> ans = new ArrayList<>();
    ans.add(1);

    PriorityQueue<pair> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(p -> p.value));
    HashSet<Integer> hashSet = new HashSet<>();

    int next_ugly_number;
    int[] indices = new int[pLen];

    for(int i=0;i<pLen;i++) {
        hashSet.add(primes[i]);
        priorityQueue.add(new pair(i,primes[i]));
    }

    while(ans.size()!=size+1)
    {
        pair pair = priorityQueue.poll();
        next_ugly_number = pair.value;
        ans.add(next_ugly_number);
        indices[pair.index]+=1;

        int temp = ans.get(indices[pair.index])*primes[pair.index];
        if (!hashSet.contains(temp))
        {
            priorityQueue.add(new pair(pair.index,temp));
            hashSet.add(temp);
        }
        else {
            while(hashSet.contains(temp))
            {
                indices[pair.index]+=1;
                 temp = ans.get(indices[pair.index])*primes[pair.index];

            }
            priorityQueue.add(new pair(pair.index,temp));
            hashSet.add(temp);

        }

    }

    ans.remove(0);
    return ans;
}

Парный класс

class pair
{
    int index,value;
    public pair(int i,int v)
    {
        index = i;
        value = v;
    }
}

Он возвращает список уродливых чисел размера size.
Я использую приоритетную очередь, чтобы найти минимум для каждого цикла, а также хеш-набор, чтобы избежать дублирования записей в priorityQueue.
Таким образом, его временная сложность равна O(n log(k)), где n — размер, а k — размер массива простых чисел.

person Rahul    schedule 10.10.2017

arrow_upward
1
arrow_downward

Это самое оптимальное решение, которое я мог бы написать с помощью динамического программирования на Python.

Временная сложность: O(n * k)

Космическая сложность: O(n)

from typing import List


def super_ugly_numbers(n: int, primes: List[int]) -> int:
    # get nth super ugly number
    ugly_nums = [0] * n
    ugly_nums[0] = 1
    length = len(primes)
    mul_indices = [0] * length
    multipliers = primes[:]

    for index in range(1, n):
        ugly_nums[index] = min(multipliers)

        for in_index in range(length):
            if ugly_nums[index] == multipliers[in_index]:
                mul_indices[in_index] += 1
                multipliers[in_index] = ugly_nums[mul_indices[in_index]] * primes[in_index]

    return ugly_nums[n-1]
person rrawat    schedule 12.07.2020

arrow_upward
0
arrow_downward

Этот алгоритм работает лучше для больших n.

primes := {2, 7, 13, 19}
set list := {1}
for i in 1..n-1:
  set k = list[0]
  for p in primes:
    insert p*k into list unless p*k is in list
  remove list[0] from list
return list[0]

Если вставка по порядку затруднена, вы можете просто вставить элементы в список в конце и отсортировать список сразу после удаления list[0].

person Charles    schedule 08.12.2015

arrow_upward
0
arrow_downward 

import java.util.*;
import java.lang.*;
import java.io.*;
public  class Solution{

    public static void main(String[] args) {
        Scanner fi = new Scanner(System.in);
        int n=fi.nextInt();
        int i;
        int primes[] ={2,3,5};
        HashSet<Integer> hm=new HashSet<>();
        PriorityQueue<Integer> pq=new PriorityQueue<>();
        TreeSet<Integer> tr=new TreeSet<>();
        tr.add(1);
        pq.add(1);
        hm.add(1);

        for (i=0;i<primes.length;i++){
            tr.add(primes[i]);
            pq.add(primes[i]);
            hm.add(primes[i]);
        }
        int size=tr.size();
        while (size < n){
            int curr=pq.poll();
            for (i=0;i<primes.length;i++){
                if (!hm.contains(curr*primes[i])) {
                    tr.add(curr * primes[i]);
                    hm.add(curr*primes[i]);
                    pq.add(curr*primes[i]);
                    size++;
                }
            }

        }
        System.out.println(tr);
    }
}

Это может помочь, поскольку TreeSet поддерживает элементы в отсортированном порядке, поэтому нужно беспокоиться об индексе.

person Kanak Singhal    schedule 01.02.2018