Эффективный алгоритм для генерации всех решений линейного уравнения диофантовом с аи = 1

Question

Я пытаюсь генерировать все решения для следующих уравнений для данного H.

С Н = 4:

1) ALL solutions for x_1 + x_2 + x_3 + x_4 =4 
2) ALL solutions for x_1 + x_2 + x_3 = 4 
3) ALL solutions for x_1 + x_2 = 4 
4) ALL solutions for x_1 =4 

Для моей проблемы всегда существует 4 уравнения (независимо от других). Существует всего 2^(H-1) решений. Для предыдущего, вот решения:

1) 1 1 1 1 
2) 1 1 2 and 1 2 1 and 2 1 1 
3) 1 3 and 3 1 and 2 2 
4) 4 

Здесь приведен алгоритм R, который решает проблему.

Однако этот алгоритм делает больше вычислений, чем необходимо. Я уверен, что можно идти быстрее. Под этим я имею в виду не создание перестановок, для которых суммы составляют> H

Любая идея лучшего алгоритма для данного H?

Answer 1

Вот в C++

blah.cpp implementation:

#include <stdlib.h> 
#include <iostream> 
#include <vector> 

using namespace std; 

vector<int> ilist; 

void diophantine(int n) 
{ 
    size_t i; 
    if (n==0) 
    { 
     for (i=0; i < ilist.size(); i++) cout << " " << ilist[i]; 
     cout << endl; 
    } 
    else 
    { 
     for (i=n; i > 0; i--) 
     { 
      ilist.push_back(i); 
      diophantine(n-i); 
      ilist.pop_back(); 
     } 
    }   
} 


int main(int argc, char** argv) 
{ 
    int n;  

    if (argc == 2 && (n=strtol(argv[1], NULL, 10))) 
    { 
     diophantine(n); 
    } 
    else cout << "usage: " << argv[0] << " <Z+>" << endl; 

    return 0; 
} 

командной строки материал:

$ g++ -oblah blah.cpp 
$ ./blah 4 
4 
3 1 
2 2 
2 1 1 
1 3 
1 2 1 
1 1 2 
1 1 1 1 
$ 

Вот в bashimplementation:

blah.sh:

#!/bin/bash 

diophantine() 
{ 
    local i 
    local n=$1 
    [[ ${n} -eq 0 ]] && echo "${ilist[@]}" || 
    { 
     for ((i = n; i > 0; i--)) 
     do 
      ilist[${#ilist[@]}]=${i} 
      diophantine $((n-i)) 
      unset ilist[${#ilist[@]}-1] 
     done    
    }  
} 

RE_POS_INTEGER="^[1-9]+$" 
[[ $# -ne 1 || ! $1 =~ $RE_POS_INTEGER ]] && echo "usage: $(basename $0) <Z+>" || 
{ 
    declare -a ilist= 
    diophantine $1 
} 
exit 0 

Вот в Python implementation

blah.py:

#!/usr/bin/python 

import time 
import sys 


def output(l): 
    if isinstance(l,tuple): map(output,l) 
    else: print l, 


#more boring faster way ----------------------- 
def diophantine_f(ilist,n): 
    if n == 0: 
     output(ilist) 
     print 
    else: 
     for i in xrange(n,0,-1): 
      diophantine_f((ilist,i), n-i) 


#crazy fully recursive way -------------------- 
def diophantine(ilist,n,i): 
    if n == 0: 
     output(ilist) 
     print 
    elif i > 0: 
     diophantine(ilist, n, diophantine((ilist,i), n-i, n-i)) 
    return 0 if len(ilist) == 0 else ilist[-1]-1 


########################## 
#main 
########################## 
try: 

    if len(sys.argv) == 1: x=int(raw_input()) 
    elif len(sys.argv) == 2: x=int(sys.argv[1]) 
    else: raise ValueError 

    if x < 1: raise ValueError 

    print "\n" 
    #diophantine((),x,x) 
    diophantine_f((),x)  
    print "\nelapsed: ", time.clock() 

except ValueError: 
    print "usage: ", sys.argv[0], " <Z+>" 
    exit(1) 

Answer 2

Я предполагаю, что вы не пытаетесь одновременно решить уравнения.

Для решения этой проблемы вы можете использовать рекурсию или динамическое программирование.

Если вы используете рекурсию, просто присвойте действительное значение первой переменной и решите ее рекурсивно.

Здесь n - количество переменных, а сумма - это сумма. cursol это частичное решение (первоначально установлен на [])

def recSolve(n,sum, cursol): 
    if n==1: 
     print cursol + [sum] 
     return 
    if n == sum: 
     print cursol + [1 for i in range(n)] 
     return 
    else: 
     for i in range(1, sum-n+2): 
      recsolve(n-1, sum-i, cursol+[i]) 

Если вы хотите использовать динамическое программирование, вы должны помнить, набор решений для каждой комбинации п и суммы.

Answer 3

Как и со многими проблемами, решение становится гораздо проще найти/исследовать, когда известна какая-либо терминология.

Решения этих проблем известны как Integer композиций, которые в перспективе обобщение разбиений (где порядок не имеет значения, то есть только ответы, которые являются уникальными в соответствии с перестановкой считаются).

Например, целочисленные перегородки 4 являются: 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2, 4, тогда как целое число композиции 4 являются : 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1, 1 + 3, 3 + 1, 2 + 2, 4.

Существует несколько вариантов реализации легко доступны (ссылки на алгоритмы языка агностика следующим образом):

• Поскольку вы работаете в R, the partitions package может генерировать разделы для йа и. Вам нужно будет найти уникальные перестановки для каждого раздела, чтобы получить композиции (см. this SO question).
• Если вы можете использовать другой язык (либо взаимодействуя с R, либо предварительно вычитая ответ), то Mathematica выполняет функцию: Compositions: Compositions.
• Sage является бесплатным (в отличие от Mathematica), а также имеет функцию генерации композиций, построенных в: Compositions. Стоит отметить, что этот реализован с использованием generators, который может использовать память более эффективно.
• Python: см. this Вопрос переполнения стека (который генерирует разделы, которые вы затем можете переставить). Я сделал что-то подобное here (хотя он использует itertools, чтобы найти перестановки, которые затем мне нужно отфильтровать для уникальных перестановок, поэтому это можно было бы сделать более эффективно, используя алгоритм перестановки специально для multisets).

Для того, чтобы понять алгоритмов лучше (или реализовать их самостоятельно), вы могли бы проверить эту неполную, но полезную книгу: Combinatorial Generation по Frank Ruskey, который показывает, как создавать разделы в постоянная амортизационного времени (CAT). Поскольку вы хотите создавать композиции, вы также можете использовать алгоритм CAT для генерации перестановок (также в книге) для генерации перестановок каждого целочисленного раздела.

RusKey также объясняет, как ранг и unrank их, что может быть удобно для хранения/хэширования результаты.

Я считаю, что они также красиво покрыты в Knuth's Art of Computer Programming Volume 4A, если вам это удобно.

ElKamina's suggestion to solve it recursively является хорошим, но я бы не использовал этот подход для больших H; начиная с R (as well as Python) doesn't optimise tail-calls, вы можете завершить переполнение стека.