我很好奇 std:next_permutation 是如何实现的，所以我提取了 gnu libstdc++ 4.7 版本并清理了标识符和格式以生成以下演示......
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
template<typename It>
bool next_permutation(It begin, It end)
{
if (begin == end)
return false;
It i = begin;
++i;
if (i == end)
return false;
i = end;
--i;
while (true)
{
It j = i;
--i;
if (*i < *j)
{
It k = end;
while (!(*i < *--k))
/* pass */;
iter_swap(i, k);
reverse(j, end);
return true;
}
if (i == begin)
{
reverse(begin, end);
return false;
}
}
}
int main()
{
vector<int> v = { 1, 2, 3, 4 };
do
{
for (int i = 0; i < 4; i++)
{
cout << v[i] << " ";
}
cout << endl;
}
while (::next_permutation(v.begin(), v.end()));
}
输出如预期:http://ideone.com/4nZdx
我的问题是:它是如何工作的？ i、j、k分别是什么意思？它们在执行的不同部分有什么值(value)？什么是其正确性证明的草图？
很明显，在进入主循环之前，它只检查琐碎的 0 或 1 元素列表案例。在主循环的入口处，我指向最后一个元素(不是一个过去的结尾)，并且列表至少有 2 个元素长。
主循环体内发生了什么？
最佳答案
让我们看一些排列:
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
...
我们如何从一种排列过渡到另一种排列？首先，让我们以不同的方式看待事物。 我们可以将元素视为数字，将排列视为数字。以这种方式查看问题我们希望以“升序”顺序排列排列/数字。
当我们订购数字时，我们希望“以最小的数量增加它们”。例如在数的时候我们不数 1,2,3,10,...，因为中间还有 4,5,...，虽然 10 大于 3，但是有缺失的数字可以通过以较小的量增加 3。在上面的示例中，我们看到 1长时间保持第一个数字，因为最后 3 个“数字”有很多重新排序，从而“增加”了较小的排列。
那么我们什么时候最终“使用”1 ?当最后 3 位数字不再有排列时。
什么时候不再有最后 3 位数字的排列？当最后 3 位按降序排列时。
啊哈!这是理解算法的关键。 只有当右边的所有内容都按降序排列时，我们才改变“数字”的位置 因为如果它不是按降序排列，那么还有更多的排列可以去 (即我们可以将排列“增加”一个较小的量)。
现在让我们回到代码:
while (true)
{
It j = i;
--i;
if (*i < *j)
{ // ...
}
if (i == begin)
{ // ...
}
}
从循环的前 2 行开始，j是一个元素，i是它之前的元素。
然后，如果元素是升序的，(if (*i < *j))做一些事情。
否则，如果整个内容按降序排列(if (i == begin))，那么这是最后一个排列。
否则，我们继续，我们看到 j 和 i 本质上是递减的。
我们现在了解 if (i == begin)部分所以我们只需要了解if (*i < *j)部分。
另请注意:“那么如果元素按升序排列......”这支持了我们之前的观察，即我们只需要对数字做一些事情“当右边的所有内容都按降序排列时”。升序if语句本质上是找到“右边的一切都按降序排列”的最左边的地方。
让我们再看一些例子:
...
1 4 3 2
2 1 3 4
...
2 4 3 1
3 1 2 4
...
我们看到当一个数字右边的所有内容都按降序排列时，我们找到下一个最大的数字并将其放在前面然后将剩余的数字按升序排列。
我们来看代码:
It k = end;
while (!(*i < *--k))
/* pass */;
iter_swap(i, k);
reverse(j, end);
return true;
好吧，因为右边的东西是按降序排列的，要找到“下一个最大的数字”，我们只需要从末尾迭代，我们在前 3 行代码中看到。
接下来，我们用 iter_swap() 将“下一个最大的数字”交换到前面。语句，然后因为我们知道数字是第二大的，所以我们知道右边的数字仍然是降序的，所以要按升序排列，我们只需要 reverse()它。
关于c++ - std::next_permutation 实现说明，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11483060/
我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server
我有一个用户工厂。我希望默认情况下确认用户。但是鉴于unconfirmed特征，我不希望它们被确认。虽然我有一个基于实现细节而不是抽象的工作实现，但我想知道如何正确地做到这一点。factory:userdoafter(:create)do|user,evaluator|#unwantedimplementationdetailshereunlessFactoryGirl.factories[:user].defined_traits.map(&:name).include?(:unconfirmed)user.confirm!endendtrait:unconfirmeddoenden
华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o
如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:
C#实现简易绘图工具一.引言实验目的:通过制作窗体应用程序(C#画图软件),熟悉基本的窗体设计过程以及控件设计,事件处理等,熟悉使用C#的winform窗体进行绘图的基本步骤,对于面向对象编程有更加深刻的体会.Tutorial任务设计一个具有基本功能的画图软件**·包括简单的新建文件,保存,重新绘图等功能**·实现一些基本图形的绘制,包括铅笔和基本形状等,学习橡皮工具的创建**·设计一个合理舒适的UI界面**注明:你可能需要先了解一些关于winform窗体应用程序绘图的基本知识,以及关于GDI+类和结构的知识二.实验环境Windows系统下的visualstudio2017C#窗体应用程序三.
MIMO技术的优缺点优点通过下面三个增益来总体概括：阵列增益。阵列增益是指由于接收机通过对接收信号的相干合并而活得的平均SNR的提高。在发射机不知道信道信息的情况下，MIMO系统可以获得的阵列增益与接收天线数成正比复用增益。在采用空间复用方案的MIMO系统中，可以获得复用增益，即信道容量成倍增加。信道容量的增加与min(Nt,Nr)成正比分集增益。在采用空间分集方案的MIMO系统中，可以获得分集增益，即可靠性性能的改善。分集增益用独立衰落支路数来描述，即分集指数。在使用了空时编码的MIMO系统中，由于接收天线或发射天线之间的间距较远，可认为它们各自的大尺度衰落是相互独立的，因此分布式MIMO
遍历文件夹我们通常是使用递归进行操作，这种方式比较简单，也比较容易理解。本文为大家介绍另一种不使用递归的方式，由于没有使用递归，只用到了循环和集合，所以效率更高一些！一、使用递归遍历文件夹整体思路1、使用File封装初始目录，2、打印这个目录3、获取这个目录下所有的子文件和子目录的数组。4、遍历这个数组，取出每个File对象4-1、如果File是否是一个文件，打印4-2、否则就是一个目录，递归调用代码实现publicclassSearchFile{publicstaticvoidmain(String[]args){//初始目录Filedir=newFile("d:/Dev");Datebeg
转自:spring.profiles.active和spring.profiles.include的使用及区别说明下文笔者讲述spring.profiles.active和spring.profiles.include的区别简介说明,如下所示我们都知道，在日常开发中,开发|测试|生产环境都拥有不同的配置信息如：jdbc地址、ip、端口等此时为了避免每次都修改全部信息，我们则可以采用以上的属性处理此类异常spring.profiles.active属性例：配置文件,可使用以下方式定义application-${profile}.properties开发环境配置文件:application-dev
通常，数组被实现为内存块，集合被实现为HashMap，有序集合被实现为跳跃列表。在Ruby中也是如此吗？我正在尝试从性能和内存占用方面评估Ruby中不同容器的使用情况 最佳答案 数组是Ruby核心库的一部分。每个Ruby实现都有自己的数组实现。Ruby语言规范只规定了Ruby数组的行为，并没有规定任何特定的实现策略。它甚至没有指定任何会强制或至少建议特定实现策略的性能约束。然而，大多数Rubyist对数组的性能特征有一些期望，这会迫使不符合它们的实现变得默默无闻，因为实际上没有人会使用它:插入、前置或追加以及删除元素的最坏情况步骤复
我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我