Tag: algorithm

Java中的迭代笛卡尔积

我想计算Java中任意数量的非空集的笛卡尔乘积。 我已经写了迭代代码… public static <T> List<Set<T>> cartesianProduct(List<Set<T>> list) { List<Iterator<T>> iterators = new ArrayList<Iterator<T>>(list.size()); List<T> elements = new ArrayList<T>(list.size()); List<Set<T>> toRet = new ArrayList<Set<T>>(); for (int i = 0; i < list.size(); i++) { iterators.add(list.get(i).iterator()); elements.add(iterators.get(i).next()); } for (int j = 1; j >= 0;) { toRet.add(Sets.newHashSet(elements)); for (j = iterators.size()-1; j >= 0 && […]

Java – 生成给定列表的幂集

我试图生成一个给定长度为N的列表的所有2 ^ N-1个可能组合的集合。该集合将组合元素的数目映射到包含特定长度的组合的有序列表。 例如，对于列表： [A, B, C, D] 我想要生成地图： { 1 -> [{A}, {B}, {C}, {D}] 2 -> [{A, B}, {A, C}, {A, D}, {B, C}, {B, D}, {C, D}] 3 -> [{A, B, C}, {A, B, D}, {A, C, D}, {B, C, D}] 4 -> [{A, B, C, D}] } 生成的数据库应保持原始顺序（其中[]表示有序的系列（ List ）， {}表示无序的组（ […]

使用一组素数按升序生成整数

我有一组素数，我只能使用这些素数因子按递增顺序生成整数。 例如，如果集合是p = {2,5}，那么我的整数应该是1,2,4,5,8,10,16,20,25 … 有没有有效的algorithm来解决这个问题？

线性时间sorting？

给定一个在[0..n ^ 3-1]范围内的n个整数的input集合，提供一个线性时间sortingalgorithm。 这是我在星期四对testing的评论，我不知道如何解决这个问题。

用最less的比较数sorting一个数组

我需要一些帮助，我的CS功课。 我需要编写一个sorting例程，在最差的情况下使用7个比较对一个长度为5的数组进行sorting（由于决策树的高度，我已经certificate需要7个）。 我考虑使用“硬编码”决策树，但这意味着algorithm非常复杂，我的导师暗示，这不是它应该做的方式。 我检查过快排，合并sorting，堆sorting，d堆sorting，插入sorting，selectsorting，都不回答要求，这导致我相信有一个长度为5的数组的特定algorithm的需要。 真的想得到一些正确方向的提示。

LINQ“OrderBy”使用什么sortingalgorithm？

显然，LINQ的“OrderBy”最初被指定为不稳定的，但到了Orca时，它被指定为稳定的。 并非所有文档都已相应更新 – 请考虑以下链接： Jon Skeet对OrderBy的稳定性 特洛伊Magennis在OrderBy稳定 但是，如果LINQ的OrderBy现在是“稳定的”，那么即使有些文档（如Troy的书）说的是这样，它意味着它不使用快速sorting（这固有地不稳定）。 所以我的问题是：如果不是快速sorting，那么LINQ的orderBy使用的algorithm是什么？

就地arrays重新sorting？

比方说，我有一个长度为n的数组，另外还有一个长度为n数组。 indices包含序列[0, n)任意排列。 我想重新排列a这样的indices指定的顺序。 例如，使用D语法： auto a = [8, 6, 7, 5, 3, 0, 9]; auto indices = [3, 6, 2, 4, 0, 1, 5]; reindexInPlace(a, indices); assert(a == [5, 9, 7, 3, 8, 6, 0]); 这可以在O（1）空间和O（n）时间内完成，最好不要改变indices ？

从数字列表中获取所有可能的组合

我正在寻找一种有效的方法来实现这一点： 你有一个数字1 ….. n列表（通常：1..5或1..7左右 – 相当小，但可以因情况而异） 你需要这些数字的所有长度的组合，例如只有一个数字（{1}，{2}，… {n}）的所有组合，那么两个不同数字（{1,2}， {1,3}，{1,4} ….. {n-1，n}），那么这些数字中的三个（{1,2,3}，{1,2,4}）等等 基本上，在组内，顺序是不相关的，所以{1,2,3}等同于{1,3,2} – 这只是从列表中获得所有x个数字组的问题 似乎应该有一个简单的algorithm – 但我迄今为止徒劳无功。 大多数组合和排列algorithm似乎a）考虑到顺序（例如123不等于132），他们总是似乎操作一个单一的string或数字…. 任何人都有一个伟大的，不错的快速algorithm，他们的袖子？ 谢谢！

有向未加权图中最长的非循环path

什么algorithm可以用来find未加权的有向无环图中最长的path？

无recursion函数调用的排列

要求：algorithm生成一个集合的所有可能的组合，不重复，或recursion调用函数返回结果。 大多数，如果不是所有的答案在JavaScript的排列提供？ 从循环或其他函数中recursion调用函数以返回结果。 循环内的recursion函数调用的示例 function p(a, b, res) { var b = b || [], res = res || [], len = a.length; if (!len) res.push(b) else for (var i = 0; i < len // recursive call to `p` here ; p(a.slice(0, i).concat(a.slice(i + 1, len)), b.concat(a[i]), res) , i++ ); return res } […]