Tìm tất cả các kết hợp của một tập hợp các số điện thoại

Question

nói rằng tôi có một tập hợp các số '0', '1', '2', ..., '9'. Tôi muốn tìm tất cả các số có chứa chính xác một trong các số trong tập hợp của tôi.

Vấn đề là: Trước khi tôi bắt đầu chương trình của mình, tôi không biết số lượng và số mà bộ của tôi sẽ bao gồm. (Ví dụ: tập hợp có thể bao gồm các số '1', '3' và '14'.)

Tôi đã tìm kiếm trên Internet, và vấp vào cụm từ 'lập trình động' mà rõ ràng là một cái gì đó để sử dụng để giải quyết vấn đề như tôi, nhưng tôi không hiểu các ví dụ.

Ai đó có thể cho tôi một gợi ý về cách giải quyết vấn đề này (có thể với lập trình động) không?

CHỈNH SỬA: Khi tập hợp bao gồm các số như '14', các số khác nhau của tập hợp sẽ phải được phân tách bằng một số phương tiện, ví dụ: khi tập hợp bao gồm các số '1', '3' và '14', các kết hợp có thể giống như 1-3-14 hoặc 3-14-1 (= số riêng biệt được phân tách bằng ký tự '-'-).

CHỈNH SỬA 2: Một vấn đề có vẻ hơi tương tự được mô tả here: một trong các giải pháp sử dụng lập trình động.

Answer 1

Để kiểm tra tất cả các kết hợp mà không biết trước có bao nhiêu chữ số phải có đầu ra, tôi đã từng viết mã này:

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

Nó làm mọi thứ chỉ trong một chu kỳ để tránh đệ quy và chức năng cuộc gọi trên không, vẫn còn nếu "giả" cần thiết lồng nhau cho các vòng bằng cách sử dụng mảng ngăn xếp.
Nó hoạt động khá tốt, trên Athlon64 3800+ 4 tuổi của tôi phải mất 2 '4' thời gian người dùng (=> thời gian tính toán thực tế) để tạo ra 36^6 = 2176782336 kết hợp, vì vậy nó tính toán khoảng 17,5 triệu kết hợp mỗi giây.

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$ 

các "thật" thời gian là khá cao bởi vì tôi cũng đang làm cái gì khác trên máy tính trong khi đó.

Answer 2

Không có gì để làm với lập trình động; trừ khi bạn muốn mặc quần lót bên ngoài quần của bạn và vẽ một biểu tượng trên ngực của bạn.

Cách đơn giản để làm điều đó là duy trì một mảng 0-9 số nguyên, sau đó chạy qua từng số một và mảng tăng [num]. Kết quả, một khi bạn đã xử lý tất cả các chữ số, là để xem nếu bất kỳ yếu tố của mảng là khác không hoặc một. (Điều đó cho biết một chữ số lặp đi lặp lại.) Tất nhiên, nó là tầm thường để có một số và sau đó lặp qua chữ số bằng chữ số sử dụng mô-đun và ước số.

Answer 3

Bạn đang tìm kiếm tất cả các hoán vị của một tập hợp các giá trị đã cho.

Một bài viết về "làm" hoán vị trong Java là ở đây: http://www.bearcave.com/random_hacks/permute.html

Bạn muốn bỏ qua cặp đôi đầu tiên của phần cho đến khi bạn nhận được để tiêu đề thuật toán hoán vị (tất nhiên).

Answer 4

Vì vậy, giả sử bạn có các số từ 1, 2 và 3.

Nếu bạn đang mong đợi sáu con số 123, 132, 213, 231, 312 và 321 để được câu trả lời đúng, những gì bạn đang tìm kiếm là một số mã để tạo ra tất cả các hoán vị của một tập hợp, điều đó sẽ nhanh hơn hầu hết mọi thứ khác cho các vấn đề về kích thước thú vị. Tuy nhiên, bạn đang xem O (n!) Là một trường hợp tốt nhất.

Answer 5

Với tôi, có vẻ như bạn đang tìm kiếm tất cả hoán vị của một tập hợp các phần tử nhất định.

Nếu bạn sử dụng C++, có chức năng chuẩn next_permutation() thực hiện chính xác những gì bạn đang tìm kiếm. Bạn bắt đầu với mảng được sắp xếp và sau đó gọi next_permutation nhiều lần.

Các ví dụ là ở đây: http://www.cplusplus.com/reference/algorithm/next_permutation/

Answer 6

Sau đây là tôi thực hiện C# 3.0 hoán vị bạn có thể tìm thấy hữu ích

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

Bạn nên wr ite một hàm đệ quy lặp qua danh sách và mỗi lần gọi chính nó với một danh sách được cập nhật. Điều này có nghĩa là nó cần tạo một bản sao của danh sách với các phần tử N-1 để chuyển sang lần lặp tiếp theo. Để có kết quả, bạn cần phải nối thêm số được chọn hiện tại trong mỗi lần lặp.

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

bao nhiêu số, và những người thân, không phải là hai câu hỏi. Nếu bạn biết số nào, bạn biết bao nhiêu.

Và tên của các số không phải là rất thú vị. 1-3-14 hoặc 0-1-2 hoặc Foo-Bar-Baz - nó luôn luôn là cùng một vấn đề, cùng một vấn đề như hoán vị của 0-1-2 và với một mảng, nơi để tìm kiếm kết quả.

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

Giải pháp thuận tiện nhất là viết một Iterable chung. Sau đó, bạn có thể sử dụng đơn giản cho vòng lặp, để truy cập mỗi hoán vị.

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