generate sequence

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.

Answer 1

[Sven]

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.

[Nicolas]

Hi Sven,

Wow I'm impressed !!! thanks a lot for your time and motivation to solve that problem, personally i would definitely not be able to create something like, so thanks again ! Speaking of the amount of data generated I knew it would be big.. but as you mentioned above I'll probably be able to better constrain the boundaries of my points (this what I'm working at the moment).. also if I use the code you've wrote in a publication you'll have to send me your detail to acknowlewdge your help !

Answer 2

[Sven]

% 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'

[Nicolas]

thanks a lot.. I have a little problem though because my data are more complex than just 4 letters and 4 positions, but I have 51 points with variable positions, and if i use the code you wrote me...

??? Maximum variable size allowed by the program is exceeded.

any idea how I could tackle the problem?

a 1 7

b 1 7

c 1 8

d 1 8

e 1 12

f 2 9

g 1 34

h 2 13

i 5 9

j 7 11

k 8 13

l 8 12

m 10 13

n 13 15

o 14 16

p 13 16

q 16 18

r 16 20

s 17 22

t 17 22

u 19 23

v 19 26

w 22 27

x 21 28

y 21 28

z 21 28

aa 23 28

ab 27 29

ac 28 31

ad 29 32

ae 28 33

af 30 33

ag 19 34

ah 33 35

ai 35 37

aj 36 38

ak 37 39

al 35 40

am 38 40

an 40 41

ao 41 42

ap 42 43

aq 28 45

ar 43 45

as 43 45

at 46 46

au 47 47

av 48 48

aw 49 49

ax 50 50

ay 51 51

Answer 3

[Sven]

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));

Answer 4

[Daniel Shub]

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.