标签: combinatorics

• 我编辑了原始文本,以节省潜在的读者一些时间和健康.也许有人会真的使用它.

我知道这是基本的东西.可能非常非常基本.
如何获得给定集合的所有可能组合.例如
string set ="abc";
我希望得到:
abc aa ab ac aaa aab aac aba abb abc aca acb acc baa bab ...
并且列表继续(如果没有设置长度限制).

我正在寻找一个非常干净的代码 - 我发现的所有东西都很脏而且工作不正常.我可以说我写的代码.

我需要这样的代码,因为我正在编写在多个线程上工作的强力(md5)实现.模式是父进程使用它们自己的组合块来提供线程,因此它们可以自己处理这些组件.
示例:第一个线程获得100个排列的包,第二个获得下一个100个等等.
让我知道我是否应该在任何地方发布最终的程序.

编辑#2再次感谢你们.
多亏了你,我已经完成了用MPICH2实现的Slave/Master Brute-Force应用程序(是的,可以在linux和windows下工作,例如网络),因为这一天几乎结束了,我已经浪费了很多时间(和太阳)我将继续我的下一个任务...... :)
你告诉我StackOverflow社区很棒 - 谢谢!

我需要创建一个函数(在R中):
- 给出N个可能的变量来赋予权重;
- 创建所有可能的权重(总计为100%);
- 受制于权重必须以P的倍数出现的约束(通常为1%)

显然,由于N和P是反向相关的 - 即我不能指定N = 7,并且P = 0.4.但是,我希望能够仅指定整数解,即P = 0.01.

很抱歉,如果这是一个众所周知的问题 - 我不是数学家,我使用我认识的术语进行了搜索,但没有发现任何足够接近的问题.

我发布了我写的代码,但是......它并不令人印象深刻或富有洞察力.

谢谢你的帮助!

假设我们有一个像那样的集合,{1,2,3}只有一种方法可以选择3个连续数字...它是集合{1,2,3} ...

对于一组{1,2,3,4},我们有3种方式: 123 234 1234

(从技术上讲,这些是无序的数字集,但连续写它们有帮助)

• f(5); {1,2,3,4,5} - > 8种方式:123 1234 1235 12345 234 2345 345 1345
• f(6); {1,2,3,4,5,6} - > 20种方式:......
• f(7); {1,2,3,4,5,6,7} - > 47种方式:......

因此对于给定的N,我可以通过应用强力,并计算具有3个或更多连续数的所有这样的子集来得到答案.

在这里,我只是想找出一种模式,一种技术来获得给定N的所有这样的子集的数量.

该问题进一步推广到.....在一组大小N内发现m个连续数.

不确定这个问题是否应该在Math-Overflow或这里,所以首先尝试这里:

假设我们给出一个N 1和M 0的数字.

存在(M + N)!/(M!*N!)个不同的这样的数字,可以在可数集合中进行排序.

例如,具有2个1和3个零的所有数字的有序集合是:

• 0 00011
• 1 00101
• 2 00110
• 3 01001
• 4 01010
• 5 01100
• 6 10001
• 7 10010
• 8 10100
• 9 11000

我们如何有效地计算相应集合中给定数字的索引？

注意:此问题的输入只是数字,而不是整个(相应)集合.

在R中,是否有一个函数返回n个元素的所有可能排序？我想要一个!通过n矩阵使得每行包含n个元素的所有可能的排序索引.也就是说,如果n = 3,我想:

 1,2,3 
 1,3,2,
 2,1,3,
 2,3,1,
 3,1,2,
 3,2,1

我首先想到expand.grid做这个工作,并尝试:

n <- 3
expand.grid(rep(list(1:n),n))

   Var1 Var2 Var3
1     1    1    1
2     2    1    1
3     3    1    1
4     1    2    1
5     2    2    1
6     3    2    1
7     1    3    1
8     2    3    1
9     3    3    1
10    1    1    2
11    2    1    2
12    3    1    2
13    1    2    2
14    2    2    2
15    3    2    2
16    1    3 …

我想计算给定$ N $元素集的每个子集的乘积之和.例如,给定集合{1,2,3},答案是1 + 2 + 3 + 1*2 + 1*3 + 2*3 + 1*2*3.我还想给出模数$ $ M $.

我所知道的是我可以计算$(x - a_1)(x - a_2)...(x - a_n) - 1 $,但这会涉及FFT,因此可能存在一些舍入误差,但主要问题是这个想法是需要$ O(N\log ^ 2 N)$时间并且模数$ M $是有问题的.有没有更快的方法来解决这个问题？这不是我的功课,我从老师那里得到了这个任务来练习编程比赛,但我真的遇到了这个问题.

约束:

$ a_i\le 10 ^ 9 $

$ N\le 10 ^ 6 $

$ M\le 10 ^ 9 $

如果我有

a=[1,3,5,7,9]
b=[2,4,6,8,10]

我想用排序创建两个列表中长度为5的每个组合.

到目前为止,我可以通过以下各种方式获得:

ab=hcat(a,b)
collect(combinations(ab,5))

但我想只收到32个(在这种情况下)有序组合.

类似于我正在寻找的函数将是Mathematica中的元组[Transpose @ {a,b}]函数.

编辑:Mathematica输出如下

a = {1, 3, 5, 7, 9};
b = {2, 4, 6, 8, 10};
combin = Tuples[Transpose@{a, b}]
Length[combin]

Out[1]:= {{1, 3, 5, 7, 9}, {1, 3, 5, 7, 10}, {1, 3, 5, 8, 9}, {1, 3, 5, 8,
10}, {1, 3, 6, 7, 9}, {1, 3, 6, 7, 10}, {1, 3, 6, 8, 9}, {1, 3, 6,
8, 10}, {1, 4, 5, 7, 9}, {1, 4, 5, …

我正在制作一个锦标赛应用程序，其中将有4个，6个或8个玩家相互对战。

它是基于回合的。因此，例如，如果总共有6个玩家，那么将有5个回合，每个回合3对。每个玩家每轮只能出现一次。

我尝试了什么

我一直在使用for循环来获取所需的组合，但是如何将这些对分成几轮以免重复呢？到目前为止，这是我所做的事情（进行每种组合）：

<?php
$players = [1,2,3,4,5,6];

for($i = 0; $i < count($players); $i++):
    for($j = 0; $j < $i; $j++):
         $pair1 = $players[$j];
         $pair2 = $players[$i];
         $pairs[] = $pair1.$pair2;          
    endfor;
endfor;
/* Output:
   [
     0 => "12"
     1 => "13"
     2 => "23"
     3 => "14"
     4 => "24"
     5 => "34"
     6 => "15"
     7 => "25"
     8 => "35"
     9 => "45"
     10 => "16"
     11 => "26"
     12 => "36"
     13 => "46"
     14 => …

我有一个mainFun其需要四个参数x,a,b,和c,所有矢量值和可能的变化长度的.这个函数调用expensiveFun计算量很大,所以我想减少调用次数expensiveFun.此功能需要被调用中的每个值x[i],a[i],b[i],c[i]和如果a,b或者c是更短的长度的话,就需要是"包装"(它们的索引是在模a[i % a.size()]).这将是最好预先计算expensiveFun的每个可能的不同值x(即所有整数0,...,MAX(X)),然后只需填写,在输出out的out[i] = precomputedValues[x[i]].如果a,b并且c具有相同的长度(例如下面的例子),这可以很容易地实现,但如果它们不是,则会变得难看.有没有什么方法可以使参数矢量长度不同的情况更有效？

下面我提供了一个可重复的例子.这是一个简化的代码,仅作为示例编写.

std::vector<int> expensiveFun(int x, int a, int b, int c) {
  std::vector<int> out(x+1);
  out[0] = a+b*c;
  for (int i = 1; i <= x; i++)
    out[i] = out[i-1] * i …

我试图在Haskell中实现列表的排列.排列的想法是这样的:

基本情况是列表长度为0和1(列表本身),当大小为2时,置换给出列表本身以及交换元素.

现在,给定一个列表[a,b,c,d],我们置换[b,c,d]并附加一个.并且我们将列表更改为第一个中的b,如[b,a,c,d]和permute [a,c,d]等,递归.

到目前为止,我已经在Haskell中完成了以下代码.哪个完美有效.但我对这包含的'haskell-ness'水平并不满意.我想提一些关于如何在haskell中使其更具可读性和效率的提示.提前致谢.代码如下:

-- swap the first element of a list with the element at the index
swapFirstWith index l | index == 0 = l
                      | otherwise =  [l!!index]
                        ++ (take (index-1) (tail l))
                        ++ [head l]
                        ++ (drop (index+1) l)


permutations :: [a] -> [[a]]
permutations [] = [[]]
permutations [a] = [[a]]
permutations [a,b] = [[a,b], [b,a]]
permutations lst = foldl (++) [] (map (\x-> miniperms x) swappedList)
    where miniperms l = map (\x-> (head …