Перебор значений из фиксированной суммы в MatLab - PullRequest
Новая
       30

Перебор значений из фиксированной суммы в MatLab

2 голосов
/ 20 марта 2012

Допустим, у меня есть n шариков, и каждый может иметь один из 8 возможных цветов Я хочу перебрать все возможные значения цветовых комбинаций мрамора. Как я могу сделать это в MatLab?

Например, если n = 2, я хочу перебрать:

2 0 0 0 0 0 0 0

1 1 0 0 0 0 0 0

1 0 1 0 0 0 0 0

1 0 0 1 0 0 0 0

1 0 0 0 1 0 0 0

1 0 0 0 0 1 0 0

1 0 0 0 0 0 1 0

1 0 0 0 0 0 0 1

0 2 0 0 0 0 0 0

0 1 1 0 0 0 0 0

0 1 0 1 0 0 0 0

и т.д.

EDIT:

Вот так будет выглядеть какой-то псевдокод, но, как вы видите, он очень неаккуратный. Я заинтересован в более кратком способе сделать это, и тот, который не нуждается в этом, если заявление ... 

for i8 = 0:1:n
    for i7 = 0:1:n - i8
        for i6 = 0:1:n - i8 - i7
            for i5 = 0:1:n - i8 - i7 - i6
                for i4 = 0:1:n - i8 - i7 - i6 - i5
                    for i3 = 0:1:n - i8 - i7 - i6 - i5 - i4
                        for i2 = 0:1:n - i8 - i7 - i6 - i5 - i4 - i3
                            for i1 = 0:1:n - i8 - i7 - i6 - i5 - i4 - i3 - i2
                                if i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 == n
                                    i = [i1, i2, i3, i4, i5, i6, i7, i8]
                                end
                            end
                        end
                    end
                end
            end
        end
    end
end

Ответы [ 5 ]

5 голосов
/ 24 марта 2012

Вот решение (код был протестирован в GNU / Octave, он должен работать и в Matlab). Этот код получен из Octave-Forge multinom_exp.m 

function conf = marbin (nmar,nbin)
%% Returns the position of nmar in nbis, allowing the marbles to be in the same bin.

%% This is standard stars and bars.
 numsymbols = nbin+nmar-1;
 stars = nchoosek (1:numsymbols, nmar);

%% Star labels minus their consecutive position becomes their index
%% position!
 idx = bsxfun (@minus, stars, [0:nmar-1]);

%% Manipulate indices into the proper shape for accumarray.
 nr = size (idx, 1);
 a = repmat ([1:nr], nmar, 1);
 b = idx';
 conf = [a(:), b(:)];
 conf = accumarray (conf, 1);
2 голосов
/ 25 марта 2012 
nc = 8;    % number colors
nm = 2;    % number marbles

% For now let marbles be unique. There are then nc^nm assignments of
% marbles to colors
nmc = nc^nm;

% Enumerate the assignments of marbles to colors: i.e., sub{k} is a row
% array giving the color of marble k for each of the nmc assignments
[sub{1:nm,1}] = ind2sub(nc*ones(1,nm),1:nmc);

% We'll use accumarray to map the marble color assignments in sub to number
% of marbles of each color
% Bring sub into form required for application of accumarray
s = mat2cell(cell2mat(sub),nm,ones(nmc,1));

% apply accumarray to each assignement of colors to marbles
a = cellfun(@(c)accumarray(c,1,[nc,1]),s,'UniformOutput',false);

% Each element of a is a column vector giving the number of marbles of each
% color. We want row vectors, and we want only the unique rows
a = unique(cell2mat(a)','rows'); 

% a is as desired.
2 голосов
/ 25 марта 2012

Я полагаю, что следующий фрагмент кода работает для случая n = 2.

Это было написано в Octave, поскольку у меня нет доступа к Matlab в настоящее время.

Я тестировал сразличные низкие значения цветов (2,3,4,5,6 и 8) в зависимости от результатов, полученных вручную. 

colours = 4;
marbles = 2;

for i=1:colours
   a = zeros(1,colours);
   a(i) = marbles
   for j=i:colours-1
      a(j) = a(j) -1;
      a(j+1) = a(j+1)+1  
   endfor
endfor

Я все еще работаю над фрагментом кода для общего случая для любого количества цветови любое количество мрамора.

2 голосов
/ 20 марта 2012

Если у вас есть 2 шарика, и каждый может иметь один из 8 возможных цветов, то этого будет достаточно: 

>> dec2base(0:63,8)
ans =
00
01
02
03
04
05
06
07
10
11
12
13
14
15
16
17
20
21
22
23
24
25
26
27
30
31
32
33
34
35
36
37
40
41
42
43
44
45
46
47
50
51
52
53
54
55
56
57
60
61
62
63
64
65
66
67
70
71
72
73
74
75
76
77

Обратите внимание, что он хранит информацию не так, как вы, но с тем жеинформация есть.Если вам это нужно, конвертировать в форму достаточно просто.

2 голосов
/ 20 марта 2012

Я думаю, что это проще, если вы думаете о состоянии мрамора, а не о состоянии цвета.Затем при необходимости преобразуйте из мраморных состояний в цветовые.Например, если вы думаете о упорядоченном списке всех возможных состояний мрамора, вы можете создать функцию, которая выглядит следующим образом (используя все нули в качестве флага «все готово»): 

function state = nextmarblestate(state, nMarbles, nColors)
%Increment the marble state by 1

%Add one to the last marble
state(end) = state(end)+1;

%Propogate change towards the first marble as colors overflow
for ixCurrent = nMarbles:-1:2
    if state(ixCurrent) > nColors;
        state(ixCurrent) = 1;
        state(ixCurrent-1) = state(ixCurrent-1)+1;
    else
        return;
    end
end

%Check to see if we are done (reset to 0)
if state(1) > nColors
    state = zeros(1,nMarbles);
end

Затем вы можете написатьбыстрый цикл, чтобы пройти через все мраморные состояния, например: 

nMarbles = 2;
nColors = 8;

marblestate = ones(1,nMarbles);
while sum(marblestate)>0
    disp(['Marblestate = [' num2str(marblestate) ']'])
    marblestate = nextmarblestate(marblestate, nMarbles, nColors);
end

Или, чтобы получить желаемый результат, напишите преобразование из мраморного состояния в цветное состояние, например так (извините за краткость здесь,это может быть расширено до более красивой версии): 

marbleState2colorState = @(marblestate) arrayfun(@(color)sum(marblestate==color), 1:nColors);

И затем, используя эту функцию преобразования, разверните вышеуказанный цикл while следующим образом: 

marblestate = ones(1,nMarbles);
while sum(marblestate)>0
    disp(['Marblestate = [' num2str(marblestate) '],  Colorstate = [' num2str(marbleState2colorState(marblestate)) ']'])
    marblestate = nextmarblestate(marblestate, nMarbles, nColors);
end

, который выдает следующий вывод: 

Marblestate = [1  1],  Colorstate = [2  0  0  0  0  0  0  0]
Marblestate = [1  2],  Colorstate = [1  1  0  0  0  0  0  0]
Marblestate = [1  3],  Colorstate = [1  0  1  0  0  0  0  0]
Marblestate = [1  4],  Colorstate = [1  0  0  1  0  0  0  0]
Marblestate = [1  5],  Colorstate = [1  0  0  0  1  0  0  0]
Marblestate = [1  6],  Colorstate = [1  0  0  0  0  1  0  0]
Marblestate = [1  7],  Colorstate = [1  0  0  0  0  0  1  0]
Marblestate = [1  8],  Colorstate = [1  0  0  0  0  0  0  1]
Marblestate = [2  1],  Colorstate = [1  1  0  0  0  0  0  0]
Marblestate = [2  2],  Colorstate = [0  2  0  0  0  0  0  0]
Marblestate = [2  3],  Colorstate = [0  1  1  0  0  0  0  0]
Marblestate = [2  4],  Colorstate = [0  1  0  1  0  0  0  0]
Marblestate = [2  5],  Colorstate = [0  1  0  0  1  0  0  0]
Marblestate = [2  6],  Colorstate = [0  1  0  0  0  1  0  0]
Marblestate = [2  7],  Colorstate = [0  1  0  0  0  0  1  0]
Marblestate = [2  8],  Colorstate = [0  1  0  0  0  0  0  1]
Marblestate = [3  1],  Colorstate = [1  0  1  0  0  0  0  0]
Marblestate = [3  2],  Colorstate = [0  1  1  0  0  0  0  0]
Marblestate = [3  3],  Colorstate = [0  0  2  0  0  0  0  0]
Marblestate = [3  4],  Colorstate = [0  0  1  1  0  0  0  0]
Marblestate = [3  5],  Colorstate = [0  0  1  0  1  0  0  0]
Marblestate = [3  6],  Colorstate = [0  0  1  0  0  1  0  0]
Marblestate = [3  7],  Colorstate = [0  0  1  0  0  0  1  0]
Marblestate = [3  8],  Colorstate = [0  0  1  0  0  0  0  1]
Marblestate = [4  1],  Colorstate = [1  0  0  1  0  0  0  0]
Marblestate = [4  2],  Colorstate = [0  1  0  1  0  0  0  0]
Marblestate = [4  3],  Colorstate = [0  0  1  1  0  0  0  0]
Marblestate = [4  4],  Colorstate = [0  0  0  2  0  0  0  0]
Marblestate = [4  5],  Colorstate = [0  0  0  1  1  0  0  0]
Marblestate = [4  6],  Colorstate = [0  0  0  1  0  1  0  0]
Marblestate = [4  7],  Colorstate = [0  0  0  1  0  0  1  0]
Marblestate = [4  8],  Colorstate = [0  0  0  1  0  0  0  1]
Marblestate = [5  1],  Colorstate = [1  0  0  0  1  0  0  0]
Marblestate = [5  2],  Colorstate = [0  1  0  0  1  0  0  0]
Marblestate = [5  3],  Colorstate = [0  0  1  0  1  0  0  0]
Marblestate = [5  4],  Colorstate = [0  0  0  1  1  0  0  0]
Marblestate = [5  5],  Colorstate = [0  0  0  0  2  0  0  0]
Marblestate = [5  6],  Colorstate = [0  0  0  0  1  1  0  0]
Marblestate = [5  7],  Colorstate = [0  0  0  0  1  0  1  0]
Marblestate = [5  8],  Colorstate = [0  0  0  0  1  0  0  1]
Marblestate = [6  1],  Colorstate = [1  0  0  0  0  1  0  0]
Marblestate = [6  2],  Colorstate = [0  1  0  0  0  1  0  0]
Marblestate = [6  3],  Colorstate = [0  0  1  0  0  1  0  0]
Marblestate = [6  4],  Colorstate = [0  0  0  1  0  1  0  0]
Marblestate = [6  5],  Colorstate = [0  0  0  0  1  1  0  0]
Marblestate = [6  6],  Colorstate = [0  0  0  0  0  2  0  0]
Marblestate = [6  7],  Colorstate = [0  0  0  0  0  1  1  0]
Marblestate = [6  8],  Colorstate = [0  0  0  0  0  1  0  1]
Marblestate = [7  1],  Colorstate = [1  0  0  0  0  0  1  0]
Marblestate = [7  2],  Colorstate = [0  1  0  0  0  0  1  0]
Marblestate = [7  3],  Colorstate = [0  0  1  0  0  0  1  0]
Marblestate = [7  4],  Colorstate = [0  0  0  1  0  0  1  0]
Marblestate = [7  5],  Colorstate = [0  0  0  0  1  0  1  0]
Marblestate = [7  6],  Colorstate = [0  0  0  0  0  1  1  0]
Marblestate = [7  7],  Colorstate = [0  0  0  0  0  0  2  0]
Marblestate = [7  8],  Colorstate = [0  0  0  0  0  0  1  1]
Marblestate = [8  1],  Colorstate = [1  0  0  0  0  0  0  1]
Marblestate = [8  2],  Colorstate = [0  1  0  0  0  0  0  1]
Marblestate = [8  3],  Colorstate = [0  0  1  0  0  0  0  1]
Marblestate = [8  4],  Colorstate = [0  0  0  1  0  0  0  1]
Marblestate = [8  5],  Colorstate = [0  0  0  0  1  0  0  1]
Marblestate = [8  6],  Colorstate = [0  0  0  0  0  1  0  1]
Marblestate = [8  7],  Colorstate = [0  0  0  0  0  0  1  1]
Marblestate = [8  8],  Colorstate = [0  0  0  0  0  0  0  2]
...