MATLAB: Generate sequence

matrix manipulationsequence

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.

Best Answer

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.
Related Question