n!在perl中生成数组的所有排列的最佳(优雅,简单,高效)方法是什么？
例如,如果我有一个数组@arr = (0, 1, 2),我想输出所有排列:
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0
它应该是一个返回迭代器的函数(延迟/延迟评估,因为它n!可能变得非常大),所以它可以这样调用:
my @arr = (0, 1, 2);
my $iter = getPermIter(@arr);
while (my @perm = $iter->next() ){
print "@perm\n";
}
我必须随机地置换长度为n的单链表的N个第一个元素.每个元素定义为:
typedef struct E_s
{
struct E_s *next;
}E_t;
我有一个根元素,我可以遍历整个大小为n的链表.什么是随机排列N个第一个元素(从根开始)最有效的技术？
因此,给定a-> b-> c-> d-> e-> f - > ... x-> y-> z我需要制作smth.像f-> a-> e-> c-> b - > ... x-> y-> z
我的具体案例:
更新:我发现了这篇论文.它声明它提出了一个O(log n)堆栈空间和预期的O(n log n)时间的算法.
我刚刚读到了关于next_permutation复杂性的另一个问题,虽然我对响应(O(n))感到满意,但似乎算法可能有一个很好的摊销分析,显示出较低的复杂性.有谁知道这样的分析？
我们给了一个字符串和字符串的排列.
例如,输入字符串sandeep和排列psdenae.
在原始字符串的排列的排序列表中查找给定排列的位置.
我有一个c++ vector与std::pair<unsigned long, unsigned long>对象。我正在尝试使用std::next_permutation(). 但是，我希望排列具有给定的大小，您知道，类似于permutationspython 中指定预期返回排列大小的函数。
基本上，c++相当于
import itertools
list = [1,2,3,4,5,6,7]
for permutation in itertools.permutations(list, 3):
print(permutation)
(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 2, 6)
(1, 2, 7)
(1, 3, 2)
(1, 3, 4)
..
(7, 5, 4)
(7, 5, 6)
(7, 6, 1)
(7, 6, 2)
(7, 6, 3)
(7, 6, 4)
(7, 6, 5)
我需要创建32位数字(有符号或无符号无关紧要,最高位永远不会被设置),每个数字必须设置给定的位数.
最简单的解决方案当然是从零开始.在循环内,数字现在增加1,计数位数,如果计数具有所需值,则数字存储到列表中,否则循环重复.如果找到足够的数字,则停止循环.当然这很好用,但是一旦所需位数变得非常高,它就会非常慢.
具有(比方说)5位的最简单的数字是设置前5位的数字.这个号码可以很容易地创建.在循环内,第一个位置位,数字向左移一个.这个循环运行5次,我找到第一个设置了5位的数字.接下来的几个数字也很容易创建.我们现在假装数字为6位宽,最高位数未设置.现在我们开始将第一个零位向右移动,因此我们得到101111,110111,111011,111101,1111110.我们可以通过在前面添加另一个0并重复此过程来重复此操作.0111110,1011110,1101110等.然而,这种方式的数字增长速度将超过必要的速度,因为使用这种简单的方法,我们省略了数字,如1010111.
那么有没有更好的方法来创建所有可能的排列,一种可以使用的通用方法,无论下一个数字将包含多少位,无论我们需要设置多少个位？
我跑过以下样本面试问题.我该如何解决？
假设我们有一个数组a1,a2,...,an,b1,b2,...,bn.
目标是在O(n)时间和O(1)空间中将此数组更改为a1,b1,a2,b2,...,an,bn.换句话说,我们需要一个线性时间算法来修改数组,只需要不超过一定量的额外存储空间.
我有一个谜题,我想用Python解决它.
难题:
一个商人的重量为40公斤,他在他的店里使用.有一次,它从他的手上掉下来,分成4块.但令人惊讶的是,现在他可以通过这4件的组合称重1公斤到40公斤之间的任何重量.
所以问题是,这4件的重量是多少？
现在我想用Python解决这个问题.
我从拼图中得到的唯一约束是4个总和是40.我可以过滤掉总和为40的所有4个值的集合.
import itertools as it
weight = 40
full = range(1,41)
comb = [x for x in it.combinations(full,4) if sum(x)==40]
length of comb = 297
现在我需要检查每组值comb并尝试所有操作组合.
例如,如果(a,b,c,d)是第一组值comb,我需要检查a,b,c,d,a+b,a-b, .................a+b+c-d,a-b+c+d........,依此类推.
我尝试了很多,但我陷入了这个阶段,即如何检查所有这些计算组合到每组4个值.
题 :
1)我想我需要列出所有可能的组合[a,b,c,d] and [+,-].
2)有没有人有更好的想法,告诉我如何从这里前进？
另外,我想完全没有任何外部库的帮助,只需要使用python的标准库.
编辑:对不起,迟到的信息.答案是(1,3,9,27),这是我几年前发现的.我检查并验证了答案.
编辑:目前,fraxel答案是完美的time = 0.16 ms.总是欢迎更好,更快的方法.
问候
方舟
之前的这个问题询问了将值1-7插入到二叉搜索树中的方法有多少,这将导致以下树:
4
/ \
2 6
/ \ / \
1 3 5 7
(顺便说一句,答案是80).
更一般地假设您获得了一个包含一组值的任意BST,并且想知道有多少可能的方法将这些值插入到最终生成结果树的BST中.有没有一种有效的算法来确定这个？
谢谢!
algorithm math permutation binary-search-tree data-structures
为什么这个简单的函数不输出输入的5个字母串的所有排列？我认为应该有120,它只输出90.
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
// Creates permutation lists for strings
vector<string> createdcombos2(string letters)
{
vector<string> lettercombos;
cout << "Letters are: " << letters << endl; //input string
do
lettercombos.push_back(letters);
while(next_permutation(letters.begin(), letters.end()));
cout <<"Letter combos: " << endl; //print out permutations
for (auto i : lettercombos)
cout << i << endl;
cout << endl << lettercombos.size() << endl; //number of permutations
return lettercombos;
}
int main()
{
string letters = "gnary";
vector<string> lettercombos; …