创建迭代(非递归)函数后，枚举 加倍受限 compositions of positive integers按照字典顺序，对于 RAM 非常少(但 EPROM 很大)的微 Controller ，我不得不将限制数量扩大到 3，即:
void GenCompositions(unsigned int myInt, unsigned int CompositionLen, unsigned int MinVal)
{
if ((MinVal = MinPartitionVal(myInt, CompositionLen, MinVal, (unsigned int) (-1))) == (unsigned int)(-1)) // Increase the MinVal to the minimum that is feasible.
return;
std::vector<unsigned int> v(CompositionLen);
int pos = 0;
const int last = CompositionLen - 1;
for (unsigned int i = 1; i <= last; ++i) // Generate the initial composition
v[i] = MinVal;
unsigned int MaxVal = myInt - MinVal * last;
v[0] = MaxVal;
do
{
DispVector(v);
if (pos == last)
{
if (v[last] == MaxVal)
break;
for (--pos; v[pos] == MinVal; --pos); //Search for the position of the Least Significant non-MinVal (not including the Least Significant position / the last position).
//std::cout << std::setw(pos * 3 + 1) << "" << "v" << std::endl; //DEBUG
--v[pos++];
if (pos != last)
{
v[pos] = v[last] + 1;
v[last] = MinVal;
}
else
v[pos] += 1;
}
else
{
--v[pos];
v[++pos] = MinVal + 1;
}
} while (true);
}
GenCompositions(10,4,1);:
7, 1, 1, 1
6, 2, 1, 1
6, 1, 2, 1
6, 1, 1, 2
5, 3, 1, 1
5, 2, 2, 1
5, 2, 1, 2
5, 1, 3, 1
5, 1, 2, 2
5, 1, 1, 3
4, 4, 1, 1
4, 3, 2, 1
4, 3, 1, 2
4, 2, 3, 1
4, 2, 2, 2
4, 2, 1, 3
4, 1, 4, 1
4, 1, 3, 2
4, 1, 2, 3
4, 1, 1, 4
3, 5, 1, 1
3, 4, 2, 1
3, 4, 1, 2
3, 3, 3, 1
3, 3, 2, 2
3, 3, 1, 3
3, 2, 4, 1
3, 2, 3, 2
3, 2, 2, 3
3, 2, 1, 4
3, 1, 5, 1
3, 1, 4, 2
3, 1, 3, 3
3, 1, 2, 4
3, 1, 1, 5
2, 6, 1, 1
2, 5, 2, 1
2, 5, 1, 2
2, 4, 3, 1
2, 4, 2, 2
2, 4, 1, 3
2, 3, 4, 1
2, 3, 3, 2
2, 3, 2, 3
2, 3, 1, 4
2, 2, 5, 1
2, 2, 4, 2
2, 2, 3, 3
2, 2, 2, 4
2, 2, 1, 5
2, 1, 6, 1
2, 1, 5, 2
2, 1, 4, 3
2, 1, 3, 4
2, 1, 2, 5
2, 1, 1, 6
1, 7, 1, 1
1, 6, 2, 1
1, 6, 1, 2
1, 5, 3, 1
1, 5, 2, 2
1, 5, 1, 3
1, 4, 4, 1
1, 4, 3, 2
1, 4, 2, 3
1, 4, 1, 4
1, 3, 5, 1
1, 3, 4, 2
1, 3, 3, 3
1, 3, 2, 4
1, 3, 1, 5
1, 2, 6, 1
1, 2, 5, 2
1, 2, 4, 3
1, 2, 3, 4
1, 2, 2, 5
1, 2, 1, 6
1, 1, 7, 1
1, 1, 6, 2
1, 1, 5, 3
1, 1, 4, 4
1, 1, 3, 5
1, 1, 2, 6
1, 1, 1, 7
void GenCompositions(unsigned int myInt, unsigned int CompositionLen, unsigned int MinVal, unsigned int MaxVal)
{
if ((MaxVal = MaxPartitionVal(myInt, CompositionLen, MinVal, MaxVal)) == 0) //Decrease the MaxVal to the maximum that is feasible.
return;
if ((MinVal = MinPartitionVal(myInt, CompositionLen, MinVal, MaxVal)) == (unsigned int)(-1)) //Increase the MinVal to the minimum that is feasible.
return;
std::vector<unsigned int> v(CompositionLen);
unsigned int last = CompositionLen - 1;
unsigned int rem = myInt - MaxVal - MinVal*(last-1);
unsigned int pos = 0;
v[0] = MaxVal; //Generate the most significant element in the initial composition
while (rem > MinVal){ //Generate the rest of the initial composition (the highest in the lexicographic order). Spill the remainder left-to-right saturating at MaxVal
v[++pos] = ( rem > MaxVal ) ? MaxVal : rem; //Saturate at MaxVal
rem -= v[pos] - MinVal; //Deduct the used up units (less the background MinValues)
}
for (unsigned int i = pos+1; i <= last; i++) //Fill with MinVal where the spillage of the remainder did not reach.
v[i] = MinVal;
if (MinVal == MaxVal){ //Special case - all elements are the same. Only the initial composition is possible.
DispVector(v);
return;
}
do
{
DispVector(v);
if (pos == last)
{
for (--pos; v[pos] == MinVal; pos--) { //Search backwards for the position of the Least Significant non-MinVal (not including the Least Significant position / the last position).
if (!pos)
return;
}
//std::cout << std::setw(pos*3 +1) << "" << "v" << std::endl; //Debug
if (v[last] >= MaxVal) // (v[last] > MaxVal) should never occur
{
if (pos == last-1) //penultimate position. //Skip the iterations that generate excessively large compositions (with elements > MaxVal).
{
for (rem = MaxVal; ((v[pos] == MinVal) || (v[pos + 1] == MaxVal)); pos--) { //Search backwards for the position of the Least Significant non-extremum (starting from the penultimate position - where the previous "for loop" has finished). THINK: Is the (v[pos] == MinVal) condition really necessary here ?
rem += v[pos]; //Accumulate the sum of the traversed elements
if (!pos)
return;
}
//std::cout << std::setw(pos * 3 + 1) << "" << "v" << std::endl; //Debug
--v[pos];
rem -= MinVal*(last - pos - 1) - 1; //Subtract the MinValues, that are assumed to always be there as a background
while (rem > MinVal) // Spill the remainder left-to-right saturating at MaxVal
{
v[++pos] = (rem > MaxVal) ? MaxVal : rem; //Saturate at MaxVal
rem -= v[pos] - MinVal; //Deduct the used up units (less the background MinValues)
}
for (unsigned int i = pos + 1; i <= last; i++) //Fill with MinVal where the spillage of the remainder did not reach.
v[i] = MinVal;
continue; //The skipping of excessively large compositions is complete. Nothing else to adjust...
}
/* (pos != last-1) */
--v[pos];
v[++pos] = MaxVal;
v[++pos] = MinVal + 1; //Propagate the change one step further. THINK: Why a CONSTANT value like MinVal+1 works here at all?
if (pos != last)
v[last] = MinVal;
}
else // (v[last] < MaxVal)
{
--v[pos++];
if (pos != last)
{
v[pos] = v[last] + 1;
v[last] = MinVal;
}
else
v[pos] += 1;
}
}
else // (pos != last)
{
--v[pos];
v[++pos] = MinVal + 1; // THINK: Why a CONSTANT value like MinVal+1 works here at all ?
}
} while (true);
}
GenCompositions(10,4,1,4);:
4, 4, 1, 1
4, 3, 2, 1
4, 3, 1, 2
4, 2, 3, 1
4, 2, 2, 2
4, 2, 1, 3
4, 1, 4, 1
4, 1, 3, 2
4, 1, 2, 3
4, 1, 1, 4
3, 4, 2, 1
3, 4, 1, 2
3, 3, 3, 1
3, 3, 2, 2
3, 3, 1, 3
3, 2, 4, 1
3, 2, 3, 2
3, 2, 2, 3
3, 2, 1, 4
3, 1, 4, 2
3, 1, 3, 3
3, 1, 2, 4
2, 4, 3, 1
2, 4, 2, 2
2, 4, 1, 3
2, 3, 4, 1
2, 3, 3, 2
2, 3, 2, 3
2, 3, 1, 4
2, 2, 4, 2
2, 2, 3, 3
2, 2, 2, 4
2, 1, 4, 3
2, 1, 3, 4
1, 4, 4, 1
1, 4, 3, 2
1, 4, 2, 3
1, 4, 1, 4
1, 3, 4, 2
1, 3, 3, 3
1, 3, 2, 4
1, 2, 4, 3
1, 2, 3, 4
1, 1, 4, 4
<= MaxVal就出现这个代码膨胀了限制？不用递归可以简化吗？#include <iostream>
#include <iomanip>
#include <vector>
void DispVector(const std::vector<unsigned int>& partition)
{
for (unsigned int i = 0; i < partition.size() - 1; i++) //DISPLAY THE VECTOR HERE ...or do sth else with it.
std::cout << std::setw(2) << partition[i] << ",";
std::cout << std::setw(2) << partition[partition.size() - 1] << std::endl;
}
unsigned int MaxPartitionVal(const unsigned int myInt, const unsigned int PartitionLen, unsigned int MinVal, unsigned int MaxVal)
{
if ((myInt < 2) || (PartitionLen < 2) || (PartitionLen > myInt) || (MaxVal < 1) || (MinVal > MaxVal) || (PartitionLen > myInt) || ((PartitionLen*MaxVal) < myInt ) || ((PartitionLen*MinVal) > myInt)) //Sanity checks
return 0;
unsigned int last = PartitionLen - 1;
if (MaxVal + last*MinVal > myInt)
MaxVal = myInt - last*MinVal; //It is not always possible to start with the Maximum Value. Decrease it to sth possible
return MaxVal;
}
unsigned int MinPartitionVal(const unsigned int myInt, const unsigned int PartitionLen, unsigned int MinVal, unsigned int MaxVal)
{
if ((MaxVal = MaxPartitionVal(myInt, PartitionLen, MinVal, MaxVal)) == 0) //Assume that MaxVal has precedence over MinVal
return (unsigned int)(-1);
unsigned int last = PartitionLen - 1;
if (MaxVal + last*MinVal > myInt)
MinVal = myInt - MaxVal - last*MinVal; //It is not always possible to start with the Minimum Value. Increase it to sth possible
return MinVal;
}
//
// Put the definition of GenCompositions() here....
//
int main(int argc, char *argv[])
{
GenCompositions(10, 4, 1, 4);
return 0;
}
最佳答案
算法
生成具有有限数量的部件和最小值和最大值的组合的迭代算法并不那么复杂。固定长度和最小值的组合实际上使事情变得更容易；我们可以始终保持每个部分的最小值，只需移动“额外”值即可生成不同的组合。
我将使用这个例子:
n=15, length=4, min=3, max=5
3,3,3,3
5,4,3,3
5,4,3,3
^
5,3,4,3
3,4,3,5
^
3,4,3,3 + 2
3,4,3,3 + 2
^
3,3,3,3 + 3
^
3,3,5,4
5,3,4,5
^
5,3,4,3 + 2
^
5,3,3,3 + 3
^
4,3,3,3 + 4
^
4,5,5,3
3,3,4,5
^
3,3,4,3 + 2
^
3,3,3,3 + 3
?
3,3,4,5是最后的组合。#include <iostream>
#include <iomanip>
#include <vector>
void DisplayComposition(const std::vector<unsigned int>& comp)
{
for (unsigned int i = 0; i < comp.size(); i++)
std::cout << std::setw(3) << comp[i];
std::cout << std::endl;
}
void Distribute(std::vector<unsigned int>& comp, const unsigned int part, const unsigned int max, unsigned int value) {
for (unsigned int p = part; value && p < comp.size(); ++p) {
while (comp[p] < max) {
++comp[p];
if (!--value) break;
}
}
}
int FindNonMinPart(const std::vector<unsigned int>& comp, const unsigned int part, const unsigned int min) {
for (int p = part; p >= 0; --p) {
if (comp[p] > min) return p;
}
return -1;
}
void GenerateCompositions(const unsigned n, const unsigned len, const unsigned min, const unsigned max) {
if (len < 1 || min > max || n < len * min || n > len * max) return;
std::vector<unsigned> comp(len, min);
Distribute(comp, 0, max, n - len * min);
int part = 0;
while (part >= 0) {
DisplayComposition(comp);
if ((part = FindNonMinPart(comp, len - 1, min)) == len - 1) {
unsigned int total = comp[part] - min;
comp[part] = min;
while (part && (part = FindNonMinPart(comp, part - 1, min)) >= 0) {
if ((len - 1 - part) * (max - min) > total) {
--comp[part];
Distribute(comp, part + 1, max, total + 1);
total = 0;
break;
}
else {
total += comp[part] - min;
comp[part] = min;
}
}
}
else if (part >= 0) {
--comp[part];
++comp[part + 1];
}
}
}
int main() {
GenerateCompositions(15, 4, 3, 5);
return 0;
}
FindNonMinPart 的电话是不必要的，因为在您重新分配值之后，您确切地知道最右边的非最小部分在哪里，并且无需再次搜索它。重新分配额外的值也可以简化，不需要函数调用。DisplayComposition 的调用显然占用了大部分时间)。#include <iostream>
#include <iomanip>
#include <vector>
void DisplayComposition(const std::vector<unsigned int>& comp)
{
for (unsigned int i = 0; i < comp.size(); i++)
std::cout << std::setw(3) << comp[i];
std::cout << std::endl;
}
void GenerateCompositions(const unsigned n, const unsigned len, const unsigned min, const unsigned max) {
// check validity of input
if (len < 1 || min > max || n < len * min || n > len * max) return;
// initialize composition with minimum value
std::vector<unsigned> comp(len, min);
// begin by distributing extra value starting from left-most part
int part = 0;
unsigned int carry = n - len * min;
// if there is no extra value, we are done
if (carry == 0) {
DisplayComposition(comp);
return;
}
// move extra value around until no more non-minimum parts on the left
while (part != -1) {
// re-distribute the carried value starting at current part and go right
while (carry) {
if (comp[part] == max) ++part;
++comp[part];
--carry;
}
// the composition is now completed
DisplayComposition(comp);
// keep moving the extra value to the right if possible
// each step creates a new composition
while (part != len - 1) {
--comp[part];
++comp[++part];
DisplayComposition(comp);
}
// the right-most part is now non-minimim
// transfer its extra value to the carry value
carry = comp[part] - min;
comp[part] = min;
// go left until we have enough minimum parts to re-distribute the carry value
while (part--) {
// when a non-minimum part is encountered
if (comp[part] > min) {
// if carry value can be re-distributed, stop going left
if ((len - 1 - part) * (max - min) > carry) {
--comp[part++];
++carry;
break;
}
// transfer extra value to the carry value
carry += comp[part] - min;
comp[part] = min;
}
}
}
}
int main() {
GenerateCompositions(15, 4, 3, 5);
return 0;
}
关于c++ - 三重限制正整数组合的非递归枚举，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56942673/
我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server
如何将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.你能做的最好的事情是:
我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我
有没有一种简单的方法可以将给定的整数格式化为具有固定长度和前导零的字符串？#convertnumberstostringsoffixedlength3[1,12,123,1234].map{|e|???}=>["001","012","123","234"]我找到了解决方案，但也许还有更聪明的方法。format('%03d',e)[-3..-1] 最佳答案 如何使用%1000而不是进行字符串操作来获取最后三位数字？[1,12,123,1234].map{|e|format('%03d',e%1000)}更新:根据theTinMan的
我有很多这样的文档:foo_1foo_2foo_3bar_1foo_4...我想通过获取foo_[X]的所有实例并将它们中的每一个替换为foo_[X+1]来转换它们。在这个例子中:foo_2foo_3foo_4bar_1foo_5...我可以用gsub和一个block来做到这一点吗？如果不是，最干净的方法是什么？我真的在寻找一个优雅的解决方案，因为我总是可以暴力破解它，但我觉得有一些正则表达式技巧值得学习。 最佳答案 我(完全)不懂Ruby，但类似这样的东西应该可以工作:"foo_1foo_2".gsub(/(foo_)(\d+)/
给定一个数组a，什么是实现其组合直到第n的最佳方法？例如:a=%i[abc]n=2#Expected=>[[],[:a],[:b],[:c],[:a,b],[:b,:c],[:c,:a]] 最佳答案 做如下:a=%w[abc]n=30.upto(n).flat_map{|i|a.combination(i).to_a}#=>[[],["a"],["b"],["c"],["a","b"],#["a","c"],["b","c"],["a","b","c"]] 关于ruby-最多n的组合，我
问题1:我无法通过以下方式找到将负整数转换为二进制的方法。我应该像这样转换它。-3=>"11111111111111111111111111111101"我在下面试过:sprintf('%b',-3)=>"..101"#..appearsanddoesnotshow111111bit.-3.to_s(2)=>"-11"#Thisjustadds-tothebinaryofthepositiveinteger3.问题2:有趣的是，如果我使用在线转换器，它告诉我-3的二进制是“0010110100110011”。"11111111111111111111111111111101"和"001
我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“
我有一个随机大小的散列，它可能有类似"100"的值，我想将其转换为整数。我知道我可以使用value.to_iifvalue.to_i.to_s==value来做到这一点，但我不确定我将如何在我的散列中递归地做到这一点，考虑到一个值可以是一个字符串，或一个数组(哈希或字符串)，或另一个哈希。 最佳答案 这是一个非常简单的递归实现(尽管必须同时处理数组和散列会增加一些技巧)。deffixnumifyobjifobj.respond_to?:to_i#IfwecancastittoaFixnum,doit.obj.to_ielsifobj
我经常迷上ruby的一件事是递归模式。例如，假设我有一个数组，它可能包含无限深度的数组作为元素。所以，例如:my_array=[1,[2,3,[4,5,[6,7]]]]我想创建一个方法，可以将数组展平为[1,2,3,4,5,6,7]。我知道.flatten可以完成这项工作，但这个问题是作为我经常遇到的递归问题的一个例子-因此我试图找到一个更可重用的解决方案。简而言之-我猜这种事情有一个标准模式，但我想不出任何特别优雅的东西。任何想法表示赞赏 最佳答案 递归是一种方法，它不依赖于语言。您在编写算法时要考虑两种情况:再次调用函数的情