当前位置： 文江博客话题详情

查找给定数字集的所有组合

发布于 2024-08-16 18:43:20 字数 499 浏览 6 评论 0原文

假设我有一组数字“0”、“1”、“2”、...、“9”。我想找到恰好包含我的集合中每个数字之一的所有数字。

问题是：在开始我的程序之前，我不知道我的集合将包含多少个数字以及哪些数字。 （例如，该集合可能包括数字“1”、“3”和“14”。）

我在互联网上搜索，偶然发现了术语“动态编程”，它显然可以用来解决像我这样的问题，但是我不明白这些例子。

有人可以给我一个关于如何解决这个问题的提示（可能使用动态编程）吗？

编辑：当该集合包含像“14”这样的数字时，该集合的不同数字当然必须通过某种方式分隔，例如，当该集合包含数字“1”、“3”和“14”时，组合可以类似于 1-3-14 或 3-14-1（= 由“-”字符分隔的各个数字）。

编辑2：此处描述了一个似乎有些相似的问题：其中一种解决方案使用动态规划。

原文

say I have a set of numbers '0', '1', '2', ..., '9'. I want to find all numbers that contain exactly one of each of the numbers in my set.

The problem is: Before I start my program, I do not know how many numbers and which numbers my set will include. (For example, the set could include the numbers '1', '3' and '14'.)

I searched the internet, and stumbled upon the term 'dynamic programming' which apparently is something to use to solve problems like mine, but I did not understand the examples.

Can somebody give me a hint on how to solve this problem (possibly with dynamic programming)?

EDIT: When the set includes numbers like '14' the different numbers of the set would of course have to be separated by some means, e.g. when the set includes the numbers '1', '3', and '14', combinations could be something like 1-3-14 or 3-14-1 (= individual numbers separated by a '-'-character).

EDIT 2: One problem that seems to be somewhat similar is described here: one of the solutions uses dynamic programming.

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（9）

溺孤伤于心 2024-08-23 18:43:20

对我来说，看起来您正在寻找给定元素集的所有排列。

如果您使用 C++，则有一个标准函数 next_permutation() 可以完全满足您的需求。您从排序后的数组开始，然后重复调用 next_permutation。

示例如下： http://www.cplusplus.com/reference/algorithm/next_permutation/

To me, it looks like you are looking for all permutations of a given set of elements.

If you use C++ there is a standard function next_permutation() that does exactly what you are looking for. You start with the sorted array and then call next_permutation repeatedly.

The example is here: http://www.cplusplus.com/reference/algorithm/next_permutation/

回复 原文
泪意 2024-08-23 18:43:20

为了在事先不知道必须有多少位输出的情况下检查所有组合，我曾经编写过这段代码：

#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 循环堆栈数组。
表现相当不错，在我的 4 年前的 Athlon64 3800+ 上，需要 2' 4" 的用户时间（=> 实际计算时间）来生成 36^6=2176782336 个组合，因此它每秒计算大约 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$

它的 “实时”时间相当长，因为我同时还在电脑上做其他事情。

To examine all the combinations without knowing in advance how many digits must have the output, I once wrote this code:

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

It does everything just in one cycle to avoid recursion and function calls overhead, still if "fakes" the needed nested for loops using the stack array.
It performs quite well, on my 4 years old Athlon64 3800+ it takes 2' 4" of user time (=> actual computation time) to generate 36^6=2176782336 combinations, so it computes about 17.5 million combinations per second.

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$

The "real" time is quite high because I was also doing something else on the PC in the meanwhile.

回复 原文
十六岁半 2024-08-23 18:43:20

您正在寻找给定值集的所有排列。

一篇关于用 Java 进行排列的文章如下： http://www.bearcave.com/ random_hacks/permute.html

您想要跳过前几个部分，直到到达标题排列算法（当然）。

You're looking to find all permutations of a given set of values.

One article on "doing" permutations in Java is here: http://www.bearcave.com/random_hacks/permute.html

You want to skip the first couple of sections until you get to the heading Permutation algorithms (of course).

回复 原文
淡淡绿茶香 2024-08-23 18:43:20

这是我的排列的 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("_"));
        }
    }

Here is my C# 3.0 implementation of permutations you can find useful

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("_"));
        }
    }
回复 原文
倚栏听风 2024-08-23 18:43:20

有多少数字和哪些数字不是两个问题。如果你知道哪些数字，你就知道有多少。

而且数字的名称也不是很有趣。 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 (")");
    }
}

How many numbers, and which ones, aren't two questions. If you know which numbers, you know how many.

And the names of the numbers aren't very interesting. 1-3-14 or 0-1-2 or Foo-Bar-Baz - it is always the same problem, the same problem as the permutations of 0-1-2 and with an array, where to look up the result.

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

The most convenient solution is, to write a generic Iterable. Then you can use the simplified for-loop, to access each permutation.

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 (")");
    }
}
回复 原文
如果没结果 2024-08-23 18:43:20

与动态规划无关；除非你想把内裤穿在裤子外面，并在胸前画一个符号。

简单的方法是维护一个 0-9 整数数组，然后逐一遍历数字并递增 array[num]。处理完所有数字后，结果是查看数组中是否有任何元素非零或一。 （这表示重复的数字。）当然，获取一个数字，然后使用模数和除数逐位迭代是很简单的。

Nothing to do with dynamic programming; unless you want to wear underpants outside your trousers and paint a symbol on your chest.

Simple way to do it is maintain an array of 0-9 of integers, then run through the numbers one by one and increment array[num]. The result, once you've processed all digits, is to see if any element of the array is non-zero or one. (That indicates a repeated digit.) Of course, it's trivial to take a number and then iterate through digit by digit using modulus and divisor.

回复 原文
没︽人懂的悲伤 2024-08-23 18:43:20

因此，假设您有数字 1、2 和 3。

如果您期望 123、132、213、231、312 和 321 这六个数字是正确答案，那么您需要的是一些代码来生成所有数字对于大小有趣的问题，这几乎比任何其他方法都要快。不过，您将 O(n!) 视为最好的情况。

So, let's say you have the numbers 1, 2 and 3.

If you are expecting the six numbers 123, 132, 213, 231, 312 and 321 to be the correct answer, what you're looking for is some code to generate all permutations of a set, that'll be faster than almost anything else for problems of an interesting size. You're looking at O(n!) as a best case, though.

回复 原文
淡淡的优雅 2024-08-23 18:43:20

您应该编写一个递归函数，循环遍历列表，并且每次都使用更新的列表调用自身。这意味着它需要创建包含 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)
   }
}

You should write a recursive function that loops through the list and every time calls itself with an updated list. This means it needs to create a copy of the list with N-1 elements to pass to the next iteration. For results, you need to append the currently selected number in each iteration.

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)
   }
}
回复 原文
彡翼 2024-08-23 18:43:20
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]

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]
回复 原文
~没有更多了~

关于作者

辞取

暂无简介

0 文章
0 评论
23 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

初遇

文章 0 评论 0

听闻余生

文章 0 评论 0

Z_dy

文章 0 评论 0

左岸枫

文章 0 评论 0

1848719402

文章 0 评论 0

婷

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文