标签: combinatorics

我有一个组合学分配,涉及从特定的字符串组合中获取长度小于或等于6的每个单词.

在这种情况下,它是S = {'a','ab','ba'}.教授刚开始将它们列出来,但我认为通过一个程序可以更容易地解决它.唯一的问题是我无法获得一个实际计算每个可能选项的好算法.

如果有人可以提供帮助,我会很感激.我通常用Python编程,但实际上我只需要帮助算法.

你能否至少给出两个例子.谢谢.

所以我坚持试图从给定的N元素集中找到所有k元素子集的问题.我知道k子集的总数是多少使用公式C(n,k)= C(n-1,k-1)+ C(n-1,k),我也知道如何做到这一点以迭代的方式,但当我试图想到一个递归的解决方案时,我陷入困境.任何人都可以给我一个提示吗？谢谢!

我得到了这个:

编写一个递归程序,给定一个没有空格的字符串,将其分解为字符串的每个可能的分段为"单词".也就是说,打印出每个可能的字符串版本,并在其中插入空格.给出分段字符串的顺序无关紧要,但必须给出所有可能的分段,不重复.

如果有人可以提供帮助,我将完全失去如何开始.

输出应该如下所示:

 Enter a string: ABCD

 ABCD
 A BCD
 A B CD
 A B C D
 A BC D
 AB CD
 AB C D
 ABC D

我有一个元素列表(让我们说整数),我需要进行所有可能的2对比较.我的方法是O(n ^ 2),我想知道是否有更快的方法.这是我在java中的实现.

public class Pair {
 public int x, y;
 public Pair(int x, int y) {
  this.x = x;
  this.y = y;
 }
}

public List<Pair> getAllPairs(List<Integer> numbers) {
 List<Pair> pairs = new ArrayList<Pair>();
 int total = numbers.size();
 for(int i=0; i < total; i++) {
  int num1 = numbers.get(i).intValue();
  for(int j=i+1; j < total; j++) {
   int num2 = numbers.get(j).intValue();
   pairs.add(new Pair(num1,num2));
  }
 }
 return pairs;
}

请注意,我不允许自配,所以应该有((n(n + 1))/ 2) - n个可能的对.我目前的工作原理,但随着n的增加,我花了很长时间才能得到这对.有没有办法将上面的O(n ^ 2)算法转换为亚二次方？任何帮助表示赞赏.

顺便说一下,我也试过下面的算法,但是当我基准测试时,根据经验,它的性能比我上面的要差.我以为通过避免内循环,这会加快速度.下面这个算法不应该更快吗？我会认为它是O(n)？如果没有,请解释并告诉我.谢谢.

public List<Pair> getAllPairs(List<Integer> …

我正在处理大量的整数排列.每个排列中的元素数量为K.元素大小为1个字节.我需要生成N个唯一的随机排列.
约束:K <= 144,N <= 1,000,000.

我想出了以下简单的算法:

1. 生成N个随机排列的列表.将所有排列存储在RAM中.
2. 对列表进行排序并删除所有重复项(如果有).重复数量相对较少.
3. 如果有任何重复项,请将随机排列添加到列表中,直到有N个排列并返回到步骤2.

有一个更好的方法吗？特别是,有没有办法不将所有排列存储在RAM中(在生成时将它们写在磁盘上)？

编辑:最后,需要按顺序访问生成的排列(逐个访问,不需要随机访问).RAM是更关键的因素(我宁愿不在RAM中同时存储所有排列).

假设我有一个包含3个数字的数组:

NSArray *array = @[@1, @2, @3];

而且我想在不重复的情况下完成所有组合.
所以我需要的是:
(1)
(2)
(3)
(1,2)
(2,3)
(1,3)
(1,2,3)

我当前的代码是这样的:

NSArray *array = @[@1, @2, @3];
int numberOfCardsOTable = [array count];

//NSLog(@"array = %@", array);

for (int lenghtOfArray = 1; lenghtOfArray <= numberOfCardsOTable; lenghtOfArray++)
{
    for (int i = 0; i < numberOfCardsOTable; i++)
    {
        // array bound check
        if (i + lenghtOfArray > numberOfCardsOTable) {
            continue;
        }

        NSArray *subArray = [[NSMutableArray alloc] init];

        subArray = [array subarrayWithRange:NSMakeRange(i, lenghtOfArray)];

        NSLog(@"array = %@", subArray); …

我必须找到对于给定单词可能的回文数字.假设这个词是.aaabbbb我的方法是

1. 准备一个不包含的哈希映射.每封信出现的时间

   对于我的例子,它将是

   a--->3
   b--->4
   

   Run Code Online (Sandbox Code Playgroud)

   1. 如果字符串的长度是偶数则没有.每个字母的出现应该是甚至形成给定单词的回文,否则回文字符的结果是0

   2. 如果字符串的长度是奇数,那么在最多一次出现的字母可以是奇数而其他字母应该是偶数.

上述两个步骤是为了找到给定单词可以形成回文的天气.

现在找不到回文字谜,我应该采用什么方法？

我是编程的新手,想在Python中询问我是否有一个m-list的条件,并想知道在if语句中是否有n个为真:

例如:

if (a == b) or (c == d) or (e == f):

将返回1,2或全部3,但我想知道其中只有2个是真的

例如:

if ((a == b) and ((c == d) or (e == f))) or (((a == b) or (c == d)) and (e == f)) or (((a == b) or (e == f)) and (c == d)):

有没有更简单的方法来做到这一点？如果(m,n)很大,该怎么办？

谢谢

给定一个整数n和k，我想创建一个大小为k的所有数组的数组，其中包含与n相加的非负整数。例如，如果k = 3且n = 10，我想要

[2,2,6]
[2,6,2]
[3,3,4]
[10,0,0]
etc....

请注意，顺序很重要，这可能会使此过程变得容易。我知道总共应该有n + k-1个选择k-1个数组。

我最初的想法是只具有k个嵌套循环，每个元素上的嵌套循环将经历0到n，然后在末尾使用if语句来检查总和是否为n。但是，这似乎很笨拙且效率很低，我想知道是否有更好的方法来实现，最好避免嵌套循环，因为我希望能够轻松地调整k。也许有相关的图书馆？我正在使用Python。

这是我对于k = 4和n = 16（糟糕）的情况：

a=0
list = []
for i in range(17):
    for j in range(17-i):
        for k in range(17-i-j):
            for l in range(17-i-j-k):
                if i+j+k+l==16:
                    list.append([i,j,k,l])
                    a += 1