Найти все комбинации заданного набора чисел

Question

say У меня есть набор чисел '0', '1', '2', ..., '9'. Я хочу найти все числа, содержащие только одно из чисел в моем наборе.

Проблема в следующем: до того, как я начну свою программу, я не знаю, сколько цифр и какие числа будет включать мой набор. (Например, набор может включать числа «1», «3» и «14».)

Я искал в Интернете и наткнулся на термин «динамическое программирование», который, по-видимому, должен что-то использовать для решения проблем как у меня, но я не понял примеров.

Может кто-нибудь дать мне подсказку о том, как решить эту проблему (возможно, с динамическим программированием)?

РЕДАКТИРОВАТЬ: Когда набор включает числа типа «14», разные номера набора, конечно, должны быть разделены каким-либо образом, например. когда набор включает числа '1', '3' и '14', комбинации могут быть примерно 1-3-14 или 3-14-1 (= индивидуальные числа, разделенные символом -'-).

EDIT 2: Одна проблема, которая кажется несколько похожей, описана here: одно из решений использует динамическое программирование.

Answer 1

Чтобы изучить все комбинации, не зная заранее, сколько цифр должно иметь выход, я когда-то писал этот код:

#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;  
} 

Он делает все только в одном цикл, чтобы избежать накладных расходов на рекурсию и функциональные вызовы, но если «подделка» необходимых вложенных циклов с использованием массива стека.
Это хорошо работает, на моем 4-летнем Athlon64 3800+ требуется 2 '4 "пользовательского времени (=> фактическое время вычисления) для создания комбинаций 36^6 = 2176782336, поэтому он вычисляет около 17,5 миллионов комбинаций в секунду.

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$ 

«реальное» время достаточно высоко, потому что я также делал что-то другое на ПК в это время.

Answer 2

Ничего общего с динамическим программированием; если вы не хотите носить трусы за пределами штанов и нарисовать символ на груди.

Простой способ сделать это - поддерживать массив из 0-9 целых чисел, а затем пронумеровать числа один за другим и увеличивать массив [num]. Результат, как только вы обработали все цифры, - это увидеть, не имеет ли какой-либо элемент массива ненулевой или один. (Это указывает на повторную цифру.) Конечно, тривиально брать число, а затем перебирать цифру по цифре с помощью модуля и делителя.

Answer 3

Вы ищете все перестановки заданного набора значений.

Одна статьи о «делать» перестановки в Java здесь: http://www.bearcave.com/random_hacks/permute.html

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

Answer 4

Итак, допустим, у вас есть номера 1, 2 и 3.

Если вы ждете шесть чисел 123, 132, 213, 231, 312 и 321, чтобы быть правильным ответом, что вы поиск - это некоторый код для генерации всех перестановок набора, который будет быстрее, чем что-либо еще для проблем интересного размера. Однако вы смотрите на O (n!) Как лучший случай.

Answer 5

Для меня это похоже, что вы ищете все перестановки заданного набора элементов.

Если вы используете C++, есть стандартная функция next_permutation(), которая выполняет именно то, что вы ищете. Вы начинаете с отсортированного массива, а затем вызываете next_permutation несколько раз.

Пример здесь: http://www.cplusplus.com/reference/algorithm/next_permutation/

Answer 6

Вот мой 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("_")); 
     } 
    } 

Answer 7

Вы должны ite рекурсивная функция, которая проходит через список и каждый раз вызывает себя с обновленным списком. Это означает, что ему необходимо создать копию списка с элементами 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) 
    } 
} 

Answer 8

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] 

Answer 9

Сколько чисел, и какие из них, не являются два вопроса. Если вы знаете, какие цифры, вы знаете, сколько.

И названия номеров не очень интересны. 1-3-14 или 0-1-2 или Foo-Bar-Baz - это всегда одна и та же проблема, та же проблема, что и перестановки 0-1-2 и с массивом, где искать результат.

idx nums words 
0 1  foo 
1 3  bar 
2 14 baz 

Наиболее удобным решением является создание общего Итерабельного. Затем вы можете использовать упрощенный for-loop для доступа к каждой перестановке.

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 (")"); 
    } 
}