如何在1乘41的1的向量中产生定位-1的20个值的每个排列? [英] how to produce every permutation of positioning 20 values of -1 in a 1-by-41 vector of ones?
问题描述
我写了不同的代码来产生一个减号的不同排列.它们适用于尺寸较小的矩阵:
例如:
S=[-1 -1 1 1 1 1 1 1];
P=unique(perms(S),'rows');
产生:
-1 -1 1 1 1 1 1 1
-1 1 -1 1 1 1 1 1
-1 1 1 -1 1 1 1 1
-1 1 1 1 -1 1 1 1
-1 1 1 1 1 -1 1 1
-1 1 1 1 1 1 -1 1
-1 1 1 1 1 1 1 -1
1 -1 -1 1 1 1 1 1
1 -1 1 -1 1 1 1 1
1 -1 1 1 -1 1 1 1
1 -1 1 1 1 -1 1 1
1 -1 1 1 1 1 -1 1
1 -1 1 1 1 1 1 -1
1 1 -1 -1 1 1 1 1
1 1 -1 1 -1 1 1 1
1 1 -1 1 1 -1 1 1
1 1 -1 1 1 1 -1 1
1 1 -1 1 1 1 1 -1
1 1 1 -1 -1 1 1 1
1 1 1 -1 1 -1 1 1
1 1 1 -1 1 1 -1 1
1 1 1 -1 1 1 1 -1
1 1 1 1 -1 -1 1 1
1 1 1 1 -1 1 -1 1
1 1 1 1 -1 1 1 -1
1 1 1 1 1 -1 -1 1
1 1 1 1 1 -1 1 -1
1 1 1 1 1 1 -1 -1
或
indices = nchoosek(1:41, 6);
N = size(indices, 1);
S = ones(N, 41);
S(sub2ind([N 41], [1:N 1:N 1:N 1:N 1:N 1:N].', indices(:))) = -1;
可以生产 6减去one(-1)和35 one(1)的所有排列的矩阵4496388_by_41.
这些代码适用于较小的尺寸，但不适用于较大尺寸的矩阵.
我的目标是产生20减去one(-1)和21 one(1)的所有排列，此矩阵有269128937220行和41列.但是以下代码不起作用:indices = nchoosek(1:41, 20);
N = size(indices, 1);
S = ones(N, 41);
S(sub2ind([N 41], [1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N].', indices(:))) = -1;
或
S=[-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1];
P=unique(perms(S),'rows');
我对每个排列(此矩阵的每一行)进行简单的计算.如果我可以使用for循环编写该矩阵的每一行，然后对该行进行计算，那么我将能够保持最佳结果，并且在这种情况下，我不必将所有这些数据都保存在内存中，不能摆脱Matlab的内存错误.
如果您知道如何使用for循环或任何其他方式将所有20减去one(-1)和21 one(1)的排列生成矩阵，或者将其存储在我的计算机中，请帮忙.
预先感谢
我不是Matlab的专家，所以我不能说所有可用资源，但是，我知道您的任务在没有任何精美的高性能服务的标准笔记本电脑，例如 https://aws.amazon.com/hpc/.
我在R中编写了一个名为RcppAlgos的软件包，该软件包能够在几个小时内轻松完成此任务.这是代码:
options(scipen = 999)
library(parallel)
library(RcppAlgos)
## WARNING Don't run this unless you have a few hours on your hand
## break up into even intervals of one million
firstPart <- mclapply(seq(1, 269128000000, 10^6), function(x) {
temp <- permuteGeneral(c(1L,-1L), freqs = c(21,20), lower = x, upper = x + 999999)
## your analysis here
x
}, mc.cores = 8)
## get the last few results and complete analysis
lastPart <- permuteGeneral(c(1L, -1L), freqs = c(21, 20),
lower = 269128000000, upper = 269128937220)
## analysis for last part goes here
为演示这种设置的效率，我们将演示完成前十亿个结果的速度.
system.time(mclapply(seq(1, 10^9, 10^6), function(x) {
temp <- permuteGeneral(c(1L, -1L), freqs = c(21, 20), lower = x, upper = x + 999999)
## your analysis here
x
}, mc.cores = 8))
user system elapsed
121.158 64.057 27.182
在30秒内获得1000000000个结果！!!!!!!
因此，这不会像@CrisLuengo计算的那样花3000多天，而是保守估计每十亿分之30秒可以得出:
(269128937220 / 1000000000 / 60) * 30 ~= 134.5645 minutes
我还应该注意，使用上述设置，您一次仅使用1251.2 Mb，因此您的内存不会爆炸.
testSize <- object.size(permuteGeneral(c(1L,-1L), freqs = c(21,20), upper = 1e6))
print(testSize, units = "Mb")
156.4 Mb ## per core
所有结果均在MacBook Pro 2.8GHz四核(具有4个虚拟核，共8个)上获得.
正如@CrisLuengo指出的那样，以上方法仅会生成大量排列，而不会考虑每次计算分析所花费的时间.经过更多的澄清和一个新的问题之后，我们现在有 answer ...大约2.5天！
I have written different code to produce different permutations of ones and minus ones. they work for matrixes with small dimensions:
for example:
S=[-1 -1 1 1 1 1 1 1];
P=unique(perms(S),'rows');
produces:
-1 -1 1 1 1 1 1 1
-1 1 -1 1 1 1 1 1
-1 1 1 -1 1 1 1 1
-1 1 1 1 -1 1 1 1
-1 1 1 1 1 -1 1 1
-1 1 1 1 1 1 -1 1
-1 1 1 1 1 1 1 -1
1 -1 -1 1 1 1 1 1
1 -1 1 -1 1 1 1 1
1 -1 1 1 -1 1 1 1
1 -1 1 1 1 -1 1 1
1 -1 1 1 1 1 -1 1
1 -1 1 1 1 1 1 -1
1 1 -1 -1 1 1 1 1
1 1 -1 1 -1 1 1 1
1 1 -1 1 1 -1 1 1
1 1 -1 1 1 1 -1 1
1 1 -1 1 1 1 1 -1
1 1 1 -1 -1 1 1 1
1 1 1 -1 1 -1 1 1
1 1 1 -1 1 1 -1 1
1 1 1 -1 1 1 1 -1
1 1 1 1 -1 -1 1 1
1 1 1 1 -1 1 -1 1
1 1 1 1 -1 1 1 -1
1 1 1 1 1 -1 -1 1
1 1 1 1 1 -1 1 -1
1 1 1 1 1 1 -1 -1
or
indices = nchoosek(1:41, 6);
N = size(indices, 1);
S = ones(N, 41);
S(sub2ind([N 41], [1:N 1:N 1:N 1:N 1:N 1:N].', indices(:))) = -1;
can produce a matrix of 4496388_by_41 of all the permutations of 6 minus one(-1) and 35 one(1).
these codes work for smaller dimensions but they don't work for the matrixs with larger dimensions.
my goal is to produce all permutations of 20 minus one(-1) and 21 one(1) this matrix has 269128937220 rows and 41 columns. but the following codes don't work:
indices = nchoosek(1:41, 20);
N = size(indices, 1);
S = ones(N, 41);
S(sub2ind([N 41], [1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N 1:N].', indices(:))) = -1;
or
S=[-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1];
P=unique(perms(S),'rows');
I do a simple calculation on each permutation(each row of this matrix). if I could write each row of this matrix with for loops and then do the calculation on that row, I would be able to keep the best result and in this situation I wouldn't have to keep all these data in the memory and I wouldn't get out of memory errors from matlab.
if you know how to produce a matrix of all the permutations of 20 minus one(-1) and 21 one(1) with for loops or any other way to store them in my computer please help.
thanks in advance
I'm not an expert in Matlab so I can't speak for all of the resources available, however, I know that your task is feasible on a standard laptop without any fancy high performance services such as https://aws.amazon.com/hpc/.
I have authored a package in R called RcppAlgos that is capable of completing this task comfortably in a few hours. Here is the code:
options(scipen = 999)
library(parallel)
library(RcppAlgos)
## WARNING Don't run this unless you have a few hours on your hand
## break up into even intervals of one million
firstPart <- mclapply(seq(1, 269128000000, 10^6), function(x) {
temp <- permuteGeneral(c(1L,-1L), freqs = c(21,20), lower = x, upper = x + 999999)
## your analysis here
x
}, mc.cores = 8)
## get the last few results and complete analysis
lastPart <- permuteGeneral(c(1L, -1L), freqs = c(21, 20),
lower = 269128000000, upper = 269128937220)
## analysis for last part goes here
And to give you a demonstration of the efficiency of this setup, we will demonstrate how fast the first one billion results are completed.
system.time(mclapply(seq(1, 10^9, 10^6), function(x) {
temp <- permuteGeneral(c(1L, -1L), freqs = c(21, 20), lower = x, upper = x + 999999)
## your analysis here
x
}, mc.cores = 8))
user system elapsed
121.158 64.057 27.182
Under 30 seconds for 1000000000 results!!!!!!!
So, this will not take over 3000 days as @CrisLuengo calculated but rather a conservative estimate of 30 seconds per billion gives :
(269128937220 / 1000000000 / 60) * 30 ~= 134.5645 minutes
I should also note that with the setup above you are only using 1251.2 Mb at a time, so your memory will not explode.
testSize <- object.size(permuteGeneral(c(1L,-1L), freqs = c(21,20), upper = 1e6))
print(testSize, units = "Mb")
156.4 Mb ## per core
All results were obtained on a MacBook Pro 2.8GHz quad core (with 4 virtual cores.. 8 total).
Edit:
As @CrisLuengo points out, the above only measures generating that many permutations and does not factor in the time taken for analysis of each computation. After some more clarification and a new question, we have that answer now... about 2.5 days!!!
这篇关于如何在1乘41的1的向量中产生定位-1的20个值的每个排列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
