Печать всей уникальной комбинации факторов заданного числа

Question

Каков наиболее эффективный алгоритм для печати всех уникальных комбинаций факторов положительного целого числа. Например, если данное число 24, то выход должен быть

24*1 
12*2 
8*3 
6*4 
6*2*2 
4*3*2 
3*2*2*2 

Вот обратите внимание, что при 6 * 4 распечатана затем 4 * 6 не получает распечатаны. Таким образом, в основном это проблема взятия уникальных подмножеств без учета порядка (один из способов взглянуть на проблему). Но цель состоит в том, чтобы иметь функцию, которая работает быстрее, поэтому сохранение факторов в структуре данных для дальнейших манипуляций может потребовать больше времени. Я попробовал свой алгоритм и вставил свой код ниже, но он, похоже, не дает мне желаемого результата, я ошибаюсь в своем рекурсивном вызове. Можете ли вы помочь мне найти эффективный способ сделать это?

public static void printfact(int num){ 
     int temp=0; 
     for(int i=num-1;i>=num/2;i--){ 
      if(num % i == 0){ 
       temp = num/i; 
       System.out.println(temp + " * " + i); 
       if(isprime(i)==false){ 
        System.out.print(temp + " * "); 
        printfact(i); 
       } 
      } 
     } 
} 

Answer 1

1) Если i < num и i > num/2, то num % i == num - i. (Легко доказать.) Таким образом, ваш цикл for бесцельно проверяет все целые числа больше num/2, а оператор if будет успешным только один раз, с temp == 2. Я не думаю, что это то, что ты хотел.

2) У вас исправлено, что рекурсия может потребовать много ответов. Но вы печатаете только temp *. Таким образом, результат будет немного странным.

3) isprime не нужно. num всегда является законным фактором, независимо от того, является ли он простым, если вы следуете приведенному ниже пункту.

4) Наконец, вам нужно выяснить, как избежать многократного копирования одной и той же факторизации. Легкое решение состоит в том, чтобы производить только факторизацию, где коэффициенты монотонно не увеличиваются (как в вашем примере). Для этого рекурсия должна производить факторизацию с некоторым максимальным коэффициентом (который был бы ранее обнаруженным множителем). Таким образом, рекурсивная функция должна иметь (по крайней мере) два аргумента: число до фактора и максимально допустимый коэффициент. (Вам также нужно решить проблему, отмеченную мной в качестве пункта 4.)

Следующий код Python (как я считаю) решает проблему, но все же имеет довольно много ненужных разделов. В отклонении от стиля python он печатает каждую факторизацию вместо того, чтобы действовать как генератор, потому что это будет легче перевести на Java.

# Uses the last value in accum as the maximum factor; a cleaner solution 
# would have been to pass max_factor as an argument. 
def factors(number, accum=[]): 
    if number == 1: 
    print '*'.join(map(str, accum)) 
    else: 
    if accum: 
     max_factor = min(accum[-1], number) 
    else: 
     max_factor = number 
    for trial_factor in range(max_factor, 1, -1): 
     remnant = number/trial_factor 
     if remnant * trial_factor == number: 
     factors(remnant, accum + [trial_factor,]) 

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

Answer 2

Этот код найти все факторы числа, сортировать их (локально и глобально):

public class PrimeFactors { 

    final SortedSet< List<Integer>> _solutions = new TreeSet<>(
     new Comparator<List<Integer>>(){ 
     @Override 
     public int compare(List<Integer> left, List<Integer> right) { 
      int count = Math.min(left.size(), right.size()); 
      for(int i = 0; i < count; ++i) { 
       if(left.get(i) < right.get(i)) { 
        return -1; 
       } 
       if(left.get(i) > right.get(i)) { 
        return +1; 
       } 
      } 
      return left.size() - right.size(); 
     }}); 

    public SortedSet< List<Integer>> getPrimes(int num) { 
     _solutions.clear(); 
     getPrimes(num, new LinkedList<Integer>()); 
     return _solutions; 
    } 

    private void getPrimes(int num, List<Integer> solution) { 
     for(int i = num - 1; i > 1; --i) { 
     if((num % i) == 0) { 
      int temp = num/i; 
      List<Integer> s = new LinkedList<>(); 
      s.addAll(solution); 
      s.add(temp); 
      s.add(i); 
      Collections.sort(s); 
      if(_solutions.add(s)) { // if not already found 
       s = new LinkedList<>(); 
       s.addAll(solution); 
       s.add(temp); 
       getPrimes(i, s); 
      } 
     } 
     } 
    } 
    public static void main(String[] args) { 
     SortedSet< List<Integer>> solutions = 
     new PrimeFactors().getPrimes(24); 
     System.out.println("Primes of 24 are:"); 
     for(List<Integer> l : solutions) { 
     System.out.println(l); 
     } 
    } 
} 

Выходы:

Primes of 24 are: 
[2, 2, 2, 3] 
[2, 2, 6] 
[2, 3, 4] 
[2, 12] 
[3, 8] 
[4, 6] 

Answer 3

Попробуйте этот рекурсивный подход, который также принимает в более 2-х входов, а именно строка, переносящая текущее значение цикла i in for для последующего восстановления, а также temp int, чтобы знать, когда не печатать повторяющиеся развороты, т.е. 8 * 3 и 3 * 8.

public static void printFactors(int number, String parentFactors, int parentVal) { 
    int newVal = parentVal; 
    for (int i = number - 1; i >= 2; i--) { 

     if (number % i == 0) { 
      if (newVal > i) { 
       newVal = i; 
      } 
      if (number/i <= parentVal && i <= parentVal 
        && number/i <= i) { 
       System.out.println(parentFactors + i + "*" + number/i); 
       newVal = number/i; 
      } 

      if (i <= parentVal) { 
       printFactors(number/i, parentFactors + i + "*", newVal); 
      } 
     } 

    } 

} 

И этот метод вызывается с помощью printFactors (12 '', 12)
Позвольте мне знать, если вы обнаружите недостатки в этом подходе. Благодаря!

Answer 4

vector<unsigned int> GetAllFactors(unsigned int number) 
{ 
    vector<unsigned int> factors; 

    for (int i = 2; i <= number; i++) 
    { 
     if (number % i == 0) 
     { 
      factors.push_back(i); 
     } 
    } 

    return factors; 
} 

void DoCombinationWithRepetitionFactors(vector<unsigned int> allFactors, unsigned currentProduct, unsigned targetProduct, vector<unsigned int> currentFactorSet, unsigned currentFactorIndex) 
{ 
    if (currentProduct == targetProduct) 
    { 
     for (auto a : currentFactorSet) 
     { 
      cout << a << " , "; 
     } 

     cout << endl; 

     return; 
    } 


    for (int i = currentFactorIndex; i < allFactors.size(); i++) 
    { 
     if (currentProduct * allFactors[i] <= targetProduct) 
     { 
      currentFactorSet.push_back(allFactors[i]); 
      DoCombinationWithRepetitionFactors(allFactors, currentProduct * allFactors[i], targetProduct, currentFactorSet, i); 
      currentFactorSet.pop_back(); 
     } 
    } 
} 

Answer 5

bool isprime(int n){ 
for(int i=2; i<=sqrt(n); i++) 
    if(n%i==0) 
     return false; 
return true; 
} 

void printprime(int n){ 

int i,j,y=n; 

while(y%2==0){ 
    cout<<"2 * "; 
    y/=2; 
} 

for(i=3; i<=sqrt(y); i+=2){ 
    while(y%i==0){ 
     cout<<i<<" * "; 
     y/=i; 
    } 
} 

if(y>2) 
    cout<<y; 
} 

void allfacs(int n){ 

int i; 
unordered_set<int> done; 

for(i=2; i<sqrt(n); i++){ 
    if(n%i==0){ 
     cout<<i<<" * "<<n/i<<endl; 

     if(!isprime(i) && done.find(i) == done.end()){ 
      done.insert(i); 
      printprime(i); 
      cout<<n/i<<endl; 
     } 
     if(!isprime(n/i) && done.find(n/i) == done.end()){ 
      done.insert(n/i); 
      cout<<i<< " * "; 
      printprime(n/i); 
      cout<<endl; 
     } 
    } 
} 
} 

Answer 6

Вот мое решение, основанное на идеях @ RICI в.

def factors(number, max_factor=sys.maxint): 
    result = [] 

    factor = min(number/2, max_factor) 
    while factor >= 2: 
     if number % factor == 0: 
      divisor = number/factor 

      if divisor <= factor and divisor <= max_factor: 
       result.append([factor, divisor]) 

      result.extend([factor] + item for item in factors(divisor, factor)) 

     factor -= 1 

    return result 

print factors(12) # -> [[6, 2], [4, 3], [3, 2, 2]] 
print factors(24) # -> [[12, 2], [8, 3], [6, 4], [6, 2, 2], [4, 3, 2], [3, 2, 2, 2]] 
print factors(157) # -> [] 

Answer 7

У меня есть решение без рекурсии или сортировки или стеков в C/C++.

#include <vector> 
#include <iostream> 

// For each n, for each i = n-1 to 2, try prod = prod*i, if prod < N. 

int 
g(int N, int n, int k) 
{ 
     int i = k; 
     int prod = n; 
     std::vector<int> myvec; 

     myvec.push_back(n); 
     while (i > 1) { 
       if (prod * i == N) { 
         prod = prod*i; 
         myvec.push_back(i); 
         for (auto it = myvec.begin(); 
           it != myvec.end(); it++) { 
           std::cout << *it << ","; 
         } 
         std::cout << std::endl; 
         return i; 
       } else if (prod * i < N) { 
         prod = prod*i; 
         myvec.push_back(i); 
       } else { i--;} 
     } 

     return k; 
} 

void 
f(int N) 
{ 
     for (int i = 2; i <= N/2; i++) { 
       int x = g(N, i, i-1); 
       // Extract all possible factors from this point 
       while (x > 0) { 
         x = g(N, i, x-1); 
       } 
     } 
} 

int 
main() 
{ 
     f(24); 

     return 0; 
} 

И выход, как это:

$ ./a.out 
    3,2,2,2, 
    4,3,2, 
    6,4, 
    6,2,2, 
    8,3, 
    12,2, 

Answer 8

Я придумал это, кажется, легко читать и понимать. Надеюсь, поможет!

def getFactors(num): 

    results = [] 

    if num == 1 or 0: 
     return [num] 

    for i in range(num/2, 1, -1): 

     if (num % i == 0): 
      divisor = num/i 

      if(divisor <= i): 
       results.append([i, divisor]) 

      innerResults = getFactors(divisor) 

      for innerResult in innerResults: 
       if innerResult[0] <= i: 
        results.append([i] + innerResult) 

    return results