generate sequence
7 次查看(过去 30 天)
显示 更早的评论
Hi,
I'm stuck with a problem trying to generate sequences with points having different possible positions within that sequence.
position name min order max order
1 A 1 4
2 B 1 3
3 C 2 4
4 D 3 4
I'm trying to write a code that would give me all possible sequences based on the min and max of each point... like ABCD, BACD and so on
I'll be very glad if anyone could help me.
Cheers,
n.
0 个评论
采纳的回答
Sven
2011-10-29
Here's the only way I think you can do your particular choice set - don't bother storing the choices in memory, just print them to the screen:
function solutionsFound = perms_bounded(choices, minBounds, maxBounds)
% Since we're only printing solutions, let's use strings
if ~iscellstr(choices)
choices = arrayfun(@num2str, choices, 'UniformOutput',false);
end
% Which choice indices can be placed in each location?
validInds = arrayfun(@(x)find(minBounds<=x & maxBounds>=x),1:length(choices),'UniformOutput',false);
setLens = cellfun(@numel,validInds);
n = length(setLens);
iSet = zeros(1, n); % Which indices of each indice set are we up to?
candSet = zeros(1,n); % What's the combination we have so far?
solutionsFound = 0;
rLevel = 1;
while 1
iSet(rLevel) = iSet(rLevel)+1;
if iSet(rLevel)>setLens(rLevel)
% We've run out of indices for this location. Exit if we're
% finished, otherwise go back one rLevel and start again.
if all(iSet>=setLens), break, end
iSet(rLevel) = 0; rLevel = rLevel-1; continue;
end
candidate = validInds{rLevel}(iSet(rLevel));
% Has this candidate already been used?
if any(candSet(1:rLevel-1)==candidate)
continue; % Already in use, try the next candidate.
else
% Place this candidate and move to the next level
candSet(rLevel) = candidate;
if rLevel<n
rLevel = rLevel+1;
else
solutionsFound = solutionsFound+1;
fprintf('#%d: %s\n',solutionsFound, sprintf('%s ',choices{candSet}))
end
end
end
Using the small set we get:
choices = {'A','B','C','D'};
minBounds = [1 1 2 3];
maxBounds = [4 3 4 4];
>> numSolutions = perms_bounded(choices, minBounds, maxBounds)
#1: A B C D
#2: A B D C
#3: A C B D
#4: B A C D
#5: B A D C
#6: B C A D
#7: B C D A
numSolutions =
7
Using the large set we get:
>> perms_bounded(choices, minBounds, maxBounds)
#1: a b c d e f g h i j k l m n o p q r s t u v w x y z aa ab ac ad ae af ag ah ai aj ak al am an ao ap aq ar as at au av aw ax ay
#2: a b c d e f g h i j k l m n o p q r s t u v w x y z aa ab ac ad ae af ag ah ai aj ak al am an ao ap aq as ar at au av aw ax ay
#3: a b c d e f g h i j k l m n o p q r s t u v w x y z aa ab ac ad ae af ag ah ai aj ak al am an ao ap ar aq as at au av aw ax ay
#4: a b c d e f g h i j k l m n o p q r s t u v w x y z aa ab ac ad ae af ag ah ai aj ak al am an ao ap ar as aq at au av aw ax ay
...
#49998: a b c d e f g h i j k l m n o p q r s t u v w x y aa z ab ac ag ad ae af ah ai al aj ak am an aq ao ap as ar at au av aw ax ay
#49999: a b c d e f g h i j k l m n o p q r s t u v w x y aa z ab ac ag ad ae af ah ai al aj ak am aq an ao ap ar as at au av aw ax ay
#50000: a b c d e f g h i j k l m n o p q r s t u v w x y aa z ab ac ag ad ae af ah ai al aj ak am aq an ao ap as ar at au av aw ax ay
#50001: a b c d e f g h i j k l m n o p q r s t u v w x y aa z ab ac ag ad ae af ah ai al aj ak aq am an ao ap ar as at au av aw ax ay
...
I've truncated the output after 50000 valid solutions. Note that choices a-through-y are still on their first valid combination. If you want to see all solutions, you may need a few weeks for it to run.
Thanks, Sven.
更多回答(3 个)
Sven
2011-10-28
% The setup
choices = {'A','B','C','D'};
minPos = [1 1 2 3];
maxPos = [4 3 4 4];
% Generate all possible combinations
choiceNums = 1:length(choices);
allPos = perms(choiceNums);
% Find entries that break the rules
tooLowMask = bsxfun(@gt, minPos(allPos), choiceNums);
tooHighMask = bsxfun(@lt, maxPos(allPos), choiceNums);
% Correct entries are those that didn't break the rules
justRight = ~any(tooHighMask | tooLowMask, 2);
validPosNums = allPos(justRight,:);
validChoices = choices(validPosNums)
validChoices =
'B' 'C' 'D' 'A'
'B' 'C' 'A' 'D'
'B' 'A' 'D' 'C'
'B' 'A' 'C' 'D'
'A' 'C' 'B' 'D'
'A' 'B' 'C' 'D'
'A' 'B' 'D' 'C'
Sven
2011-10-29
Ack... I had a feeling you were talking about high-dimensionality.
Daniel is 100% correct - 51^51 is huge. Even if you only consider combinations of numbers within your given range of minBound->maxBound you get a very large number of possible combinations:
prod(arrayfun(@(x)nnz(minBounds<=x & maxBounds>=x),1:length(choices)))
ans =
1.1694e+035
This number is still too large for a brute force approach. I have tried an iterative-brute force approach below, where at each iteration I generate all possible combinations and cull out the bad ones before moving on. It's neither optimal (as in, it could be improved to conserve memory) nor optimised (as in, it could be made faster), but I believe it's correct. It takes a similar approach to Daniel's suggestion, in that it fills in entries in order of how constrained they are. It doesn't bother checking for the no-solution - that could be added. I tried at every opportunity to conserve memory - using uints instead of doubles and loops instead of nicer MATLAB tricks. Nevertheless, on my 32bit machine I ran out of memory only 25 columns into the 51-choice array.
Keep in mind that even if you can get it to run, your final and correct answer will still be a huge matrix - a matrix of many many millions by 51. Any adjustment you can make to the min/max bounds (making them tighter or reducing the number of choices) would help it along the way, but here it is anyway:
function out = perms_bounded(choices, minBounds, maxBounds)
minBounds = minBounds(:)';
maxBounds = maxBounds(:)';
validInds = arrayfun(@(x)find(minBounds<=x & maxBounds>=x),1:length(choices),'UniformOutput',false);
% Attack locations by the most constrained to least constrained
[~,sortIdxs] = sort(cellfun(@numel, validInds));
P = validInds{sortIdxs(1)}';
for rLevel = 2:length(choices)
validUp2Now = P;
oldSz = size(validUp2Now,1);
thisInds = validInds{sortIdxs(rLevel)};
thisSz = length(thisInds);
P = zeros(oldSz * thisSz, rLevel, 'uint8');
% To replace the repmat call below (which hogs memory), try a loop
% P(:,1:rLevel-1) = repmat(validUp2Now, thisSz, 1);
for i = 1:thisSz
P((i-1)*oldSz+1:i*oldSz,1:rLevel-1) = validUp2Now;
end
clear validUp2Now
thisMat = ones(oldSz,1,'single')*thisInds;
P(:,rLevel) = thisMat(:);
clear thisMat
% Use a loop instead of the cleaner bsxfun, to save memory
% hasDupMask = any(bsxfun(@eq, P(:,1:rLevel-1), P(:,rLevel)),2);
hasDupMask = false(size(P(:,1)));
for i = 1:rLevel-1
hasDupMask = hasDupMask | P(:,i)==P(:,rLevel);
end
P(hasDupMask,:) = [];
end
out = choices(P(:,sortIdxs));
0 个评论
Daniel Shub
2011-10-28
Presumably your 51 elements are highly constrained (51^51 is a big number). If your constraints are such that you can generate them all in a reasonable time and only require a reasonable amount of memory, I would try and solve the problem recursively. I would sort the elements based on the tightness of the constraints and place the most contained elements first and the least constrained elements last. Basically place the first element and asking for all valid combinations of the other 50 elements. You get those by placing the new first element and asking for all valid combinations of the other 49 elements. I don't have time to write code, but I don't think it will be too hard.
My intuition tells me that there is probably some really cool sexy solution using a sparse matrix and the intersection of your constraints. N-D geometry is hard for me so I don't know how i would do this.
0 个评论
另请参阅
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!