数字のセット「0」、「1」、「2」、...、「9」があるとします。セット内の各番号の1つだけを含むすべての番号を検索したいと思います。
問題は次のとおりです。プログラムを開始する前に、セットに含まれる数字の数と数字がわかりません。（たとえば、セットには「1」、「3」、「14」の数字を含めることができます。）
インターネットを検索して、私のような問題を解決するために使用するものと思われる「動的計画法」という用語に出くわしましたが、例がわかりませんでした。
誰かがこの問題を解決する方法についてのヒントを教えてもらえますか（おそらく動的計画法で）？
編集：セットに「14」のような数字が含まれている場合、もちろん、セットの異なる数字は何らかの手段で分離する必要があります。たとえば、セットに「1」、「3」、および「14」の数字が含まれている場合、組み合わせは次のようになります。 1-3-14または3-14-1（='-'-文字で区切られた個々の数字）のようなものにします。
編集2：やや似ていると思われる問題の1つをここで説明します。解決策の1つは、動的計画法を使用します。
私には、特定の要素セットのすべての順列を探しているように見えます。
next_permutation()C++ を使用している場合、探していることを正確に実行する標準関数があります。next_permutationソートされた配列から始めて、繰り返し呼び出します。
例はここにあります: http://www.cplusplus.com/reference/algorithm/next_permutation/
出力が必要な桁数を事前に知らずにすべての組み合わせを調べるために、私はかつて次のコードを書きました。
#include <stdio.h>
#include <stdlib.h>
#define ARRSIZE(arr) (sizeof(arr)/sizeof(*(arr)))
int main()
{
const char values[]= {'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char * buffer=NULL;
int * stack=NULL;
int combinationLength=-1;
int valuesNumber=-1;
int curPos=0;
fprintf(stderr, "%s", "Length of a combination: ");
if(scanf("%d", &combinationLength)!=1 || combinationLength<1)
{
fputs("Invalid value.\n",stderr);
return 1;
}
fprintf(stderr, "%s (%lu max): ", "Possible digit values",(long unsigned)ARRSIZE(values));
if(scanf("%d", &valuesNumber)!=1 || valuesNumber<1 || (size_t)valuesNumber>ARRSIZE(values))
{
fputs("Invalid value.\n", stderr);
return 1;
}
buffer=(char *)malloc(combinationLength);
stack=(int *)malloc(combinationLength*sizeof(*stack));
if(buffer==NULL || stack==NULL)
{
fputs("Cannot allocate memory.\n", stderr);
free(buffer);
free(stack);
return 2;
}
/* Combinations generator */
for(;;)
{
/* If we reached the last digit symbol... */
if(stack[curPos]==valuesNumber)
{
/* ...get back to the previous position, if we finished exit */
if(--curPos==-1)
break;
/* Repeat this check */
continue;
}
buffer[curPos]=values[stack[curPos]];
/* If we are in the most inner fake-cycle write the combination */
if(curPos==combinationLength-1)
puts(buffer);
stack[curPos]++;
/* If we aren't on the last position, start working on the next one */
if(curPos<combinationLength-1)
{
curPos++;
stack[curPos]=0;
}
}
/* Cleanup */
free(buffer);
free(stack);
return 0;
}
スタック配列を使用して必要なネストされた for ループを「偽装」する場合でも、再帰と関数呼び出しのオーバーヘッドを回避するために、すべてを 1 サイクルで実行します。
私の 4 年前の Athlon64 3800+ では、36^6=2176782336 の組み合わせを生成するのに 2 フィート 4 インチのユーザー時間 (=> 実際の計算時間) がかかるため、1 秒あたり約 1750 万の組み合わせを計算します。
matteo@teoubuntu:~/cpp$ gcc -Wall -Wextra -ansi -pedantic -O3 combinations.c -o combinations.x
matteo@teoubuntu:~/cpp$ time ./combinations.x > /media/Dati/combinations.txt
Length of a combination: 6
Possible digit values (36 max): 36
real 13m6.685s
user 2m3.900s
sys 0m53.930s
matteo@teoubuntu:~/cpp$ head /media/Dati/combinations.txt
000000
000001
000002
000003
000004
000005
000006
000007
000008
000009
matteo@teoubuntu:~/cpp$ tail /media/Dati/combinations.txt
zzzzzq
zzzzzr
zzzzzs
zzzzzt
zzzzzu
zzzzzv
zzzzzw
zzzzzx
zzzzzy
zzzzzz
matteo@teoubuntu:~/cpp$ ls -lh /media/Dati/combinations.txt
-rwxrwxrwx 1 root root 15G 2010-01-02 14:16 /media/Dati/combinations.txt
matteo@teoubuntu:~/cpp$
その間、私は PC で別のこともしていたので、「リアルタイム」時間はかなり高くなっています。
与えられた値のセットのすべての順列を見つけようとしています。
Javaでの順列の「実行」に関する1つの記事は、次のとおりです。http: //www.bearcave.com/random_hacks/permute.html
（もちろん）「順列アルゴリズム」という見出しに到達するまで、最初の2、3のセクションをスキップします。
これが、役立つと思われる順列のC＃3.0実装です
public static class PermutationExpressions
{
public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> list)
{
return list.Permutations((uint)list.Count());
}
public static IEnumerable<IEnumerable<T>> Permutations<T>(this IList<T> list)
{
return list.Permutations((uint)list.Count);
}
private static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> list, uint n)
{
if (n < 2) yield return list;
else
{
var ie = list.GetEnumerator();
for (var i = 0; i < n; i++)
{
ie.MoveNext();
var item = ie.Current;
var i1 = i;
var sub_list = list.Where((excluded, j) => j != i1).ToList();
var sub_permutations = sub_list.Permutations(n - 1);
foreach (var sub_permutation in sub_permutations)
{
yield return
Enumerable.Repeat(item, 1)
.Concat(sub_permutation);
}
}
}
}
}
[TestFixture]
public class TestPermutations
{
[Test]
public void Permutation_Returns_Permutations()
{
var permutations = PermutationExpressions.Permutations(new[] { "a", "b", "c" }.AsEnumerable());
foreach (var permutation in permutations)
{
Console.WriteLine(string.Join("", permutation.ToArray()));
}
Assert.AreEqual("abc_acb_bac_bca_cab_cba", permutations.Select(perm => perm.joinToString("")).joinToString("_"));
}
}
いくつの数字とどれがどれかは 2 つの問題ではありません。どの数字かがわかれば、いくつあるかがわかります。
そして、数字の名前はあまり興味深いものではありません。1-3-14 または 0-1-2 または Foo-Bar-Baz - それは常に同じ問題であり、0-1-2 の順列と同じ問題であり、結果をどこで検索するかという配列を使用します。
idx nums words
0 1 foo
1 3 bar
2 14 baz
最も便利な解決策は、一般的な Iterable を作成することです。次に、単純化された for ループを使用して、各順列にアクセスできます。
import java.util.*;
class PermutationIterator <T> implements Iterator <List <T>> {
private int current = 0;
private final long last;
private final List <T> lilio;
public PermutationIterator (final List <T> llo) {
lilio = llo;
long product = 1;
for (long p = 1; p <= llo.size (); ++p)
product *= p;
last = product;
}
public boolean hasNext () {
return current != last;
}
public List <T> next () {
++current;
return get (current - 1, lilio);
}
public void remove () {
++current;
}
private List <T> get (final int code, final List <T> li) {
int len = li.size ();
int pos = code % len;
if (len > 1) {
List <T> rest = get (code / len, li.subList (1, li.size ()));
List <T> a = rest.subList (0, pos);
List <T> res = new ArrayList <T> ();
res.addAll (a);
res.add (li.get (0));
res.addAll (rest.subList (pos, rest.size ()));
return res;
}
return li;
}
}
class PermutationIterable <T> implements Iterable <List <T>> {
private List <T> lilio;
public PermutationIterable (List <T> llo) {
lilio = llo;
}
public Iterator <List <T>> iterator () {
return new PermutationIterator <T> (lilio);
}
}
class PermutationIteratorTest {
public static void main (String[] args) {
List <Integer> la = Arrays.asList (new Integer [] {1, 3, 14});
PermutationIterable <Integer> pi = new PermutationIterable <Integer> (la);
for (List <Integer> lc: pi)
show (lc);
}
public static void show (List <Integer> lo) {
System.out.print ("(");
for (Object o: lo)
System.out.print (o + ", ");
System.out.println (")");
}
}
動的計画法とは何の関係もありません。ズボンの外にパンツを着て、胸にシンボルを描きたい場合を除きます。
これを行う簡単な方法は、0〜9の整数の配列を維持してから、数値を1つずつ実行し、array[num]をインクリメントすることです。すべての桁を処理した後の結果は、配列のいずれかの要素がゼロ以外または1であるかどうかを確認することです。（これは、数字が繰り返されることを示します。）もちろん、数値を取得してから、モジュラスと除数を使用して数字ごとに繰り返すのは簡単です。
つまり、1、2、3の数字があるとしましょう。
6つの数字123、132、213、231、312、および321が正解であると期待している場合、探しているのは、セットのすべての順列を生成するコードです。これは、他のほとんどのものよりも高速です。興味深いサイズの問題の場合。ただし、O（n！）を最良のケースとして見ています。
リストをループし、更新されたリストで自分自身を呼び出すたびに、再帰関数を作成する必要があります。これは、次の繰り返しに渡すために N-1 個の要素を持つリストのコピーを作成する必要があることを意味します。結果を得るには、各反復で現在選択されている数値を追加する必要があります。
string Permutations(List numbers, string prefix)
{
foreach (current_number in numbers)
{
new_prefix = prefix+"-"+number;
new_list=make_copy_except(numbers, current_number)
if (new_list.Length==0)
print new_prefix
else
Permutations(new_list, new_prefix)
}
}
import Data.List (inits, tails)
place :: a -> [a] -> [[a]]
place element list = zipWith (\front back -> front ++ element:back)
(inits list)
(tails list)
perm :: [a] -> [[a]]
perm = foldr (\element rest -> concat (map (place element) rest)) [[]]
test = perm [1, 3, 14]