4

与えられたHについて、次の方程式のすべての解を生成しようとしています。

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アルゴリズムです。

library(gtools)
H<-4
solutions<-NULL

for(i in seq(H))
{
    res<-permutations(H-i+1,i,repeats.allowed=T)
    resum<-apply(res,1,sum)
    id<-which(resum==H)

    print(paste("solutions with ",i," variables",sep=""))
    print(res[id,])
}

ただし、このアルゴリズムは必要以上の計算を行います。もっと速く行くことは可能だと確信しています。つまり、合計が>Hである順列を生成しないことを意味します

与えられたHのためのより良いアルゴリズムのアイデアはありますか？

4

3 に答える 3

5

多くの問題と同様に、いくつかの用語がわかっていると、解決策を見つけたり調べたりするのがはるかに簡単になります。

これらの問題の解決策は、整数構成として知られています。これは、整数パーティションの一般化です（順序は重要ではありません。つまり、順列の下で一意の回答のみが考慮されます）。

たとえば、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で作業しているため、partitionsパッケージでパーティションを生成できます。構成を取得するには、各パーティションの一意の順列を見つける必要があります（このSOの質問を参照）。
  • 別の言語を使用できる場合（Rとのインターフェース、または回答の事前計算のいずれかによって）、Mathematicaにはコンポジションを計算する関数がありますCompositions。
  • Sageは（Mathematicaとは異なり）無料であり、以下に組み込まれているコンポジションを生成する機能もありますCompositions。これは、メモリをより効率的に使用できるジェネレータを使用して実装されていることに注意してください。
  • Python：このStack Overflowの質問を参照してください（パーティションを生成し、それを並べ替えることができます）。私はここで同様のことをしました（ただし、順列を見つけるために使用し、次に一意の順列をフィルタリングする必要があるため、マルチセットitertools専用の順列アルゴリズムを使用することで、これをより効率的に行うことができます）。

アルゴリズムをよりよく理解する（または自分で実装する）ために、この不完全ですが便利な電子ブック： FrankRuskeyによるCombinatorialGenerationをチェックしてください。これは、一定の償却時間（CAT）でパーティションを生成する方法を示しています。コンポジションが必要なため、CATアルゴリズムを使用して順列を生成し（本でも）、各整数パーティションの順列を生成することもできます。

Ruskeyは、それらをランク付けおよびランク付け解除する方法についても説明しています。これは、結果の保存/ハッシュに便利です。

もしあなたがそれを手元に持っていれば、これらはクヌースのコンピュータプログラミングの芸術第4A巻でもうまくカバーされていると思います。

それを再帰的に解決するというElKaminaの提案は良いものですが、私はこのアプローチを大きなHには使用しません。R（およびPython）は末尾呼び出しを最適化しないため、スタックオーバーフローが発生する可能性があります。

于 2013-02-15T04:32:06.877 に答える
2

これがC++での実装です

blah.cpp：

#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
$


これがの実装ですbash：

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での実装です

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)
于 2012-06-06T01:42:13.443 に答える
0

方程式を同時に解こうとしているのではないと思います。

これを解決するには、再帰または動的計画法のいずれかを使用できます。

再帰を使用している場合は、最初の変数に有効な値を割り当て、残りの変数を再帰的に解決するだけです。

ここで、nは変数の数であり、sumは合計です。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])

動的計画法を使用する場合は、nとsumの各組み合わせの解のセットを覚えておく必要があります。

于 2012-05-16T15:13:29.930 に答える