标签: combinatorics

这是一个组合学问题,需要一些哈希算法的理论.

假设输入可以是30 kB到5 MB大小的任意随机字节序列(我想这会产生很多输入值的组合:))

对于不同的文件,从字节序列计算的MD5哈希的前4个字节(或前n个字节)的概率是多少？

如果不能专门为MD5哈希计算,那么生成均匀分布的m字节哈希值的任何哈希函数在给定输入范围的前n个字节上计算哈希与冲突的概率是多少？

我正在寻找一种算法,用于找到从0到5的整数的最简单组合(即由最少数量的整数组成的整数),这些整数尚未使用(所使用的组合在列表中).

订单确实很重要,组合应该在列表中返回.

例如,使用过的数字的列表可能如下所示:

{{0},{1},{2},{3},{4},{0,0},{0,1},{0,2},...,{2,1},{ 2,2},...,{1,5,4},...}

在这种情况下,算法应该返回一个{5}的列表,因为{5}是由最少的整数组成的组合.

如果列表如下所示:

{{0},{1},{2},{3},{4},{5},{0,0},{0,1},{0,2},{0,3},{ 0,5},...}

算法应该返回一个0和4({0,4})的列表.

由于它将在Java中使用,因此Java答案是可取的,但伪代码或其他编程语言也是可用的.

先感谢您!

背景:我有一个带一些参数的函数.我想为所有可能的参数组合提供函数的结果.

一个简化的例子:

f <- function(x, y) { return paste(x, y, sep=",")} 
colors = c("red", "green", "blue") 
days = c("Monday", "Tuesday") 

我希望我的结果看起来像

     color    day         f    
[1,] "red"    "Monday"    "red,Monday" 
[2,] "red"    "Tuesday"   "red,Tuesday"
[3,] "green"  "Monday"    "green,Monday"
[4,] "green"  "Tuesday"   "green,Tuesday"
[5,] "blue"   "Monday"    "blue,Monday"
[6,] "blue"   "Tuesday"   "blue,Tuesday"

我的想法是创建一个带有列的矩阵,color并day使用现有向量填充它,colors并days为结果初始化一个空列,然后使用循环为每个矩阵行调用f一次,并将结果写入最后一列.但我不知道如何轻松地生成从基体colors和days载体.我尝试搜索它,但我得到的所有结果都是针对该combn功能的,它做了不同的事情.

在这个简化的案例中,colors和days是因素,但在我的实例中,情况并非如此.函数的一些参数是整数,所以我的真实矢量可能看起来更像1, 2, 3,并且函数将要求它作为数字传递给它.所以请不要依赖于因子级别的解决方案,如果它们不能以某种方式用于处理整数.

我有一个正在进行的调查Fibonacci序列的项目,这只是一个个人项目,我创建了一个二进制文件tree class,它创建了Fibonacci调用图的二叉树,所以f(3)我生成了树:

我想创建一个tree class get_partitions()遍历树的方法来生成分区root value,我在这里看到的顺序不同的顺序作为不同的分区; 所以对于这里的例子f(3),该get_partitions()方法将遍历树并产生:

Partion 1: 2,1
Partion 2: 2,1,0
Partion 3: 1,1,1
Partion 4: 1,1,1,0
Partion 5: 1,0,1,1
Partion 6: 1,0,1,1,0

最后,我想列举Fibonacci数的每个排列root value,在这种情况下3,对于Partition 1枚举的分区将是(2,1),(1,2),或者Partion 2将被枚举(2,1,0),(2,0,1),(1,2,0),(1,0,2),(0,2,1),(0,1,2),等等......

[编辑1]我关心的是Partion 4,并Partion 5在这方面的例子如列举这些partions的所有组合会产生重复 partions.

给定的组合数量root value会产生加泰罗尼亚数字是否正确？

我Tree class是:

class FibTree(object):
"""Class which builds binary tree from …

多集是一个集合,其中所有元素可能不唯一.如何枚举集合元素中的所有可能的排列？

给定一个具有n个元素的集合,我需要找到该集合中具有几乎相等大小的k个子集的所有分区.

例如,对于具有7个元素和3个子集的集合,我只需要分区,其中有两个子集,每个子​​集有2个元素,一个子集有3个元素.我不希望分区具有1,2和4个元素的子集.

换句话说,一组7个元素有877个可能的分区,但我只对105(？)分区感兴趣,这些分区由2/2/3个元素构成子集:

实际上,n大约为35,这意味着大约有2.81*10 ^27个分区,"仅" 8,338,573,669,964,101个分区有三个子集.因此,我不可能全部计算它们并趟过去找到我想要的那些.

什么算法只计算感兴趣的分区？(不是分区数,而是每个分区的每个子集中的实际成员.)

任何人都可以详细说明这段代码的一些细节,甚至可以给出这个算法的非Linq版本:

public static IEnumerable<IEnumerable<T>> Combinations<T>
    (this IEnumerable<T> elements, int k)
{
   return k == 0 ? new[] { new T[0] }
                 : elements.SelectMany(
                       (e, i) =>
                         elements
                         .Skip(i + 1)
                         .Combinations(k - 1)
                         .Select(c => (new[] {e}).Concat(c)));
}

对于一组表格A = {1, 2, 3, ..., n}.它被称为集合的分区,是A一组k<=n尊重以下定理的元素:

a)所有分区的A并集是A

b)2个分区的交集A是空集(它们不能共享相同的元素).

例如.A = {1, 2,... n}我们有分区: {1, 2, 3} {1, 2} {3} {1, 3} {2} {2, 3} {1} {1} {2} {3}

这些理论概念在我的算法教科书中提出(顺便说一下,这个子章节是"回溯"章节的一部分).我应该找到一个算法来生成给定集合的所有分区.我整天都在努力解决这个问题,但我找不到解决办法.你能解释一下这个算法是如何工作的吗？另外,你能给我一个算法的伪代码草图吗？

有一个有n个帖子的围栏,每个帖子都可以涂上一种k颜色.您必须绘制所有帖子,使得不超过两个相邻的栅栏柱具有相同的颜色.返回可以绘制栅栏的总方式.

diff - 具有不同颜色的组合的数量,
相同 - 具有相同颜色的组合的数量,
n - 发布的数量,
k - 颜色的数量.

对于n = 1:

diff = k;
same = 0;

对于n = 2:

diff = k * (k - 1);
same = k;

对于n = 3:

diff = (k + k * (k - 1)) * (k - 1);
same = k * (k - 1);

最后的公式是:

diff[i] = (diff[i - 1] + diff[i - 2]) * (k - 1);
same[i] =  diff[i - …

对于可能包含零个或多个连字符的字符串,我需要使用和不使用连字符提取所有不同的可能性.

例如,字符串"AB"将导致"AB"和"AB"(两种可能性).

字符串"ABC"将产生"ABC","AB-C","A-BC"和"ABC"(四种可能性).

字符串"ABCD"将产生"ABCD","AB-CD","A-BC-D","AB-CD","AB-CD","ABC-D","A-BCD"和"ABCD"(八种可能性).

......等等

我已经尝试了一些嵌套循环但是无法获得所需的结果.我怀疑我需要一些递归的东西,除非有一些我忽略的简单解决方案.

NB.这是为了构建一个SQL查询(遗憾的是SQL Server没有MySQL的REGEXP模式匹配).

这是我正在努力的一次尝试.如果我以递归方式执行此操作,这可能会有效.

string keyword = "A-B-C-D";

List<int> hyphens = new List<int>();

int pos = keyword.IndexOf('-');
while (pos != -1)
{
    hyphens.Add(pos);
    pos = keyword.IndexOf('-', pos + 1);
}

for (int i = 0; i < hyphens.Count(); i++)
{
    string result = keyword.Substring(0, hyphens[i]) + keyword.Substring(hyphens[i] + 1);

    Response.Write("<p>" + result);
}

ABCD是不同长度的单词.