首页 文章
  • 8 votes
     answers
     views

    生成集合[1]的所有分区

    对于A = {1, 2, 3, ..., n}形式的集合。这称为集合A的分区,集合k<=n的元素遵循以下定理: a)A所有分区的并集是A b)A的 2 个分区的交集是空集(它们不能共享相同的元素)。 例如。 A = {1, 2,... n}我们有分区:{1, 2, 3} {1, 2} {3} {1, 3} {2} {2, 3} {1} {1} {2} {3} 这些理论概念已在我的算法教科书中...
  • 3 votes
     answers
     views

    整数分区[1]

    正整数 n 的分区是正整数的 non-increasing 数组 a [2],a [3],...,a [4] 满意 a [5] a [6] ... a [7] = n。 m 称为该分区的长度。 我们可以按指定顺序列出 n 的所有分区。例如,如果我们使用词典顺序对所有英语单词进行排序的规则,则称为词典顺序。另一种方式,如果我们使用 C 语言比较字符串的规则,则称为反向词典顺序。还有一个 colex ...
  • 64 votes
     answers
     views

    Haskell 中 2 个列表的笛卡尔积

    我希望在 Haskell 中产生 2 个列表的笛卡尔积,但是我不知道该怎么做。笛卡尔积提供列表元素的所有组合: xs = [1,2,3] ys = [4,5,6] cartProd :: [a] -> [b] -> [(a,b)] cartProd xs ys ==> [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]...
  • 5 votes
     answers
     views

    如何获得 R 中向量的所有可能分区的列表?

    假设我有一个唯一元素的 R 向量,例如x <- c(1,2,3,4,5)。 是否有一个函数可以给我该向量x的所有可能分区的列表?我猜每个分区都是一个向量列表,其中x中的每个元素都属于其中一个向量。我希望将所有可能的分区分成任意数量的任何大小的集合。 (我认为此类分区的数量类似于2^n * n!,其中n是唯一元素的数量.我可能不会在具有 4 个以上唯一 elements.)的向量上不使用此函数...
  • 5 votes
     answers
     views

    在 R 中将向量详尽划分为成对的方法

    (这是受到另一个标记为重复的问题的启发。尽管我可能是 ignorant.),但我还是认为这是一个有趣的问题,尽管组合方法可能有一个简单的解决方案。 问题 对于长度为n的向量,其中n mod 2为零,请找到所有可能的方法将向量的所有元素划分为对,而无需替换,顺序无关紧要。 例如,对于向量c(1,2,3,4): list(c(1,2), c(3,4)) list(c(1,3), c(2,4)) lis...
  • 2 votes
     answers
     views

    大小为 K 的整数分区

    给定一个F non-negative 个整数的向量v,我想要一个一个地创建大小为F且总和为v的所有可能的K向量集。我称 C 为这 K 个向量的矩阵。 C 的行总和为v。 例如,如果设置为 K=2,则大小为 F=2 的向量(1,2)可以分解为: # all sets of K vectors such that their sum is (1,2) C_1 = 1,0 C_2 = 1,0 C_...
  • 0 votes
     answers
     views

    大小为 K 的整数向量组成(以 C 表示)

    整数v的组成是 K 个整数的集合,这样它们的总和为v(并且顺序很重要)。例如,2 的 3-sized 组成为: 2 0 0 1 1 0 1 0 1 0 2 0 0 1 1 0 0 2 可以找到一个简单的 C 算法以获得这些成分这里: void print(std::vector<int>& a) { std::ostream_iterator<int&...
  • 37 votes
     answers
     views

    Code-golf:生成帕斯卡的三角形

    生成一个列表列表(或打印,我不介意),其大小为 N,且行数最少的帕斯卡的三角形! 这是我的尝试(在 python 2.6 **中使用一个恶作剧的 118 个字符): c,z,k=locals,[0],'_[1]' p=lambda n:[len(c()[k])and map(sum,zip(z+c()[k][-1],c()[k][-1]+z))or[1]for _ in range(n)] 说明...
  • 1 votes
     answers
     views

    以递归方式返回子集 - Python

    我必须实现一个递归函数,它只收到两个参数:'n'和'k',其中n是从'0'到'n-1'的集合的长度,k是子集的长度原始集合中的不同元素 . 我们必须最后返回一个列表列表,其中包含k长度的所有子列表 . 我不知道要克服的扭曲是我们不能使用其他参数,如列表,元组,集等等...... 所以我不知道如何在递归中“保存”所有子集的列表而没有“丢失”的细节 . def ret_k_subset(n, k)...
  • -1 votes
     answers
     views

    将输入输入c数组时出现运行时错误

    我正在编写一个编程问题(Uva#11330 https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=2305&mosmsg=Submission+received+with+ID+20947216)并且我...
  • 7 votes
     answers
     views

    最小化'swapping'的最小变化算法

    这是一个关于非数学家的组合学的问题,所以请尽量忍受我! 给定n个不同字符的数组,我想以最小变化顺序生成k个字符的子集,即生成i 1恰好包含一个不在第i代中的字符的顺序 . 这本身并不太难 . 但是,我还想最大化在第i代中交换的字符 out 与第i代交换 in 的字符数相同的情况 . 为了说明,对于n = 7,k = 3: abc abd abe * abf * abg * afg aeg * ad...
  • 1 votes
     answers
     views

    寻找有关理解特定组合优化问题的建议

    给定一组项目(大小在1到100之间)和多个箱子(1到15) . 每个项目具有可以分配项目的箱子集,并且优先排序哪个箱子最好,第二好,等等,只是为了它 . 项目也有一个自然顺序,下面用命名表示,例如item2之前的item1 . 每个箱子的容量在1到5之间(每个物品具有相同的重量,即1) . 一个示例输入可以是三个箱子和六个物品( - 表示箱子不在物品的可用集合中,即不能用它打包): | bin1 ...
  • 1 votes
     answers
     views

    用于覆盖具有M的子集的M的k组合的集合的算法

    我正在研究一个应用程序,我想要获取M中所有可能的元素k组合的集合C(带|| M || = m),并用子集的k组合覆盖C M的N_i,|| N_i || = n <m∀N_i 因此,有(m选择k)组合要覆盖,并且n个元素的每个集合Q_i将包含(n选择k)组合 . 我想要的是一种构造集合Qi的算法,使得q被最小化(即,尽可能接近(m选择k)/(n选择k)) 因此,例如,如果m = 100,k =...
  • 4 votes
     answers
     views

    在Python中用数字获取子集族的有效方法

    我有一个n元素集,我想考虑其固定大小为s的k元素子集的族 . 例如,如果n = 3,k = 1,s = 2,我们有以下系列: {{1}, {2}}, {{1}, {3}}, {{2}, {3}} 在我的问题中,k,s不是那么小,例如s = n = 50,k = 20 . 让我们说所有这些家庭都按字典顺序排列(或者按照任何明确规定的顺序排列) . 我希望有一种有效的方式来获得一个家庭的数量 . 我...
  • 8 votes
     answers
     views

    从文件内容计算的MD5哈希的前4个字节会发生冲突的概率是多少?

    这是一个组合学问题,需要一些哈希算法的理论 . 假设输入可以是30 kB到5 MB大小的任意随机字节序列(我想这会产生很多输入值的组合:)) 对于不同的文件,从字节序列计算的MD5哈希的前4个字节(或前n个字节)的概率是多少? 如果不能专门为MD5哈希计算,那么生成均匀分布的m字节哈希值的任何哈希函数在给定输入范围的前n个字节上计算哈希与冲突的概率是多少?
  • 4 votes
     answers
     views

    Pigeonhole问题:将不同类型的UIImage放入UIImageViews

    假设我有10个盒子和4种不同类型的彩球:黑色,蓝色,红色,绿色 . 我想在10个盒子中以大致相等的比例分配不同颜色的球 . 例如,一个可接受的解决方案是在10个盒子中放置2个黑色,2个蓝色,3个红色和3个绿色球 . 现在,更具体地说,假设我有10个UIImageViews,以及可变数量的UIImages(Facebook,Twitter,Flickr等)放入这些UIImageViews中 . 如果...
  • -1 votes
     answers
     views

    算法:如何均匀分布不同颜色的球?

    假设我有一些不同颜色的球 . 为了举个例子,我们假设有4个红球,4个蓝球和2个绿球 . 如果我想均匀分布这些球,以便保持两个相同颜色的球之间的最一致的距离,我可以有以下顺序: R-B-G-R-B-R-B-G-R-B 尽管蓝色和红色球与其对应球的距离并不总是相同,但它们的排列方式使得它们的距离保持一致,同时保持了绿球的一致性 . 在6个红球,5个蓝球和3个绿球的情况下,我可以有类似的东西: R-B-...
  • 3 votes
     answers
     views

    是否有算法打印阵列的所有子序列?

    我正在使用组合学,我想知道是否有一个算法打印给定数组的子序列的所有布置 . 也就是说,如果我给这个算法的序列“ABCDEF”它将打印: A,B,C,D,E,F,AB,AC,AD,AE,AF,BC,BD,BE,BF,CD,CE,CF,DE,DF,EF,ABC,ABD,ABE,ABF,ACD,ACE,ACF,ADE,ADF,AEF,BCD,BCE,BCF,BDE,BDF,BEF,CDE,CDF,CEF...
  • 0 votes
     answers
     views

    将一个集合划分为正好k个块[关闭]

    我需要一种算法来生成集合S的所有分区为 exactly k <| S |块 . 注意:我已经找到了生成所有可能分区的算法;我只需要 k - partition algorithm . 任何的想法?
  • 4 votes
     answers
     views

    分区设置使得笛卡尔积遵守约束

    我正在阅读this question,其中描述了以下问题陈述: 你有两个整数:N和K.Lun狗对满足以下条件的字符串感兴趣:字符串有N个字符,每个字符都是'A'或'B' . 字符串s恰好具有K对(i,j)(0 <= i <j <= N-1),使得s [i] ='A'并且s [j] ='B' . 如果存在满足条件的字符串,则查找并返回任何此类字符串 . 否则,返回一个空字符串 ...
  • 0 votes
     answers
     views

    R软件中的分区按照输入向量中提供的大小顺序打印

    考虑索引集{1,...,n} . 我想在R软件中找到一个函数,它接收一个非负整数的向量{x [1],...,x [k]},并产生上面所有可能分区的列表作为输出提到的索引设置,使得该分区的第一个元素是一组大小为x [1],分区的第二个元素是一组大小为x [2],...,以及第k个元素 . partition是一组大小x [k] . 我注意到R软件中的函数listParts创建了{1,...,n}的...
  • 1 votes
     answers
     views

    在迭代器上调用next()操作两次

    背景: 我正在尝试编写将识别对称分区的代码 . 我有一个分区和反向分区功能,它将按顺序打印出分区,反过来 即分区3:[[3],[2,1],[1,1,1]]和反向分区3:[[1,1,1],[2,1],[3]] 我的目标是编写一个程序,它将匹配分区函数的子列表的第一个位置中的整数(所以3,2和1),并将其与我的反向子列表中每个元素的数量相匹配分区(因此代码将[3]和[1,1,1]视为相同,并为两者计数...
  • 1 votes
     answers
     views

    IBM Cplex中对称旅行商的子消除约束

    IBM Cplex中有一个旅行商问题的示例代码 . 它将subour排除约束定义为: forall (s in subtours) sum (i in Cities : s.subtour[i] != 0) x[<minl(i, s.subtour[i]), maxl(i, s.subtour[i])>] <= s.size-1; 有人可以用这个...
  • 2 votes
     answers
     views

    如何有效地生成总和在指定范围内的所有组合(在所有深度)

    假设您有一组值( 1 , 1 , 1 , 12 , 12 , 16 ),您将如何生成所有可能的组合(不重复),其总和在预定义范围 [min,max] 内 . 例如,以下是 13 和 17 之间范围的所有组合(所有深度): 1 12 1 1 12 1 1 1 12 16 1 16 这假设具有相同值的每个项目都是无法区分的,因此在最终输出中没有三个结果 1 12 . ...
  • 0 votes
     answers
     views

    集合的分区 - 存储导致一系列嵌套列表

    我有代码将列出一组的所有分区 . 代码来自此站点:Generating the Partitions of a Set . 我不想只打印出分区,而是将它们存储为列表 . 我想在这个递归示例中返回的内容之后对我的结果进行建模:How to find all partitions of a set . 我想要一个整数列表的列表 . 内部列表是中间列表中包含的分区的子集,外部列表包含所有分区的完整集合 ...
  • 464 votes
     answers
     views

    如何在Python中生成列表的所有排列

    如何在Python中生成列表的所有排列,与该列表中的元素类型无关? 例如: permutations([]) [] permutations([1]) [1] permutations([1, 2]) [1, 2] [2, 1] permutations([1, 2, 3]) [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1...
  • 1 votes
     answers
     views

    将矩阵排列成唯一的行和列

    说我有一个矢量, vec <- c(rep(1,4),rep(2,4),rep(3,4),rep(4,4),rep(5,4),rep(6,4),rep(7,4),rep(8,4),rep(9,4)) 我安排了一个矩阵6x6 . mat <- matrix(vec,6,byrow=T) [,1] [,2] [,3] [,4] [,5] [,6] [1,] 1 1...
  • 16 votes
     answers
     views

    在Perl中,如何生成列表的所有可能组合?

    我有一个带有列表的文件,需要创建一个文件,将每行与另一行进行比较 . 例如,我的文件有这个: AAA BBB CCC DDD EEE 我希望最终列表看起来像这样: AAA BBB AAA CCC AAA DDD AAA EEE BBB CCC BBB DDD BBB EEE CCC DDD CCC EEE DDD EEE ...
  • 1 votes
     answers
     views

    随机访问固定字母表中3个符号的有序集合的枚举

    想象一下,我们有一个字母表,例如5个字符: ABCDE . 我们现在想要列举所有可能的3组这些字母 . 每个字母只能出现一次,字母的顺序无关紧要(因此集合中的字母应该排序) . 所以我们得到以下几组: ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE 共10套 . 该命令是词典 . 现在假设字母长度为 N (本例中为5),...
  • 2 votes
     answers
     views

    对于有两名以上参赛者的轮次,什么算法可以生成Round-Robin“配对”?

    我希望能够产生一组锦标赛对决,使得每个玩家至少面对对方一次,每个玩家玩相同数量的游戏 . 可以把它想象成马里奥卡丁车的循环赛对决的抽象 . 在我的情况下,我有17名参赛者,并希望他们参加3或4名选手的比赛 . 我想有办法生成S,一组P(玩家)的子集,这样P的每个元素都出现在S的至少一个元素中,而P的每个元素都是 . 起初我认为 balancer 锦标赛设计会回答,但似乎没有任何方法可以匹配每一轮的...

热门问题