Здравствуйте, Ароан, Вы писали:
А>Добрый день.
А>Подскажите быстрый алгоритм упорядочивания сочетаний.
По сочетанию номер надо получить? Тогда так:
int index(vector<int> v, int N)
{
sort(v.begin(), v.end());
int res = 0;
for (int i=0, j=1; i < v.size(); j++)
{
if (v[i] == j)
i++;
else
res += C[N - j][v.size() - i - 1];
}
return res + 1;
}
Нужно получить сочетание по номеру, или быстро последовательно перебрать их?
Если перебрать, то вот:
// массив x[k], элементы которого лежат в [0..n) и ∀i : x[i] & x[i] < x[i+1]void init_combination(int* x, int n, int k)
{
assert(k<=n);
for(int i=0; i<k; ++i) x[i] = i;
}
bool next_combination(int* x, int n, int k) // инкремент как можно более правого элемента...
{
assert(k<=n);
// находим хвост, который уже невозможно инкрементироватьint i=k-1, j=n-1;
while(x[i]==j) { --i; --j; }
if(i<0) return false; // весь массив инкрементирован до упора, больше нечего итерировать
// инкрементируем предшествующий элемент (его индекс как раз i)
j = ++x[i];
// устанавливаем хвостовые элементы в минимальные значения
++i, ++j;
while(i<n) { x[i]=j; ++i; ++j; }
return true; // можно итерировать далее
}
......
vector<int> x (k);
init_combination(&x[0], n, k);
do
{
// пользуемся...
}
while(next_combination(&x[0], n, k);
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Ароан, Вы писали:
К>Нужно получить сочетание по номеру, или быстро последовательно перебрать их?
Вообще-то и то и другое, но критично именно получить НОМЕР по сочетанию.
То что предложил Vintik_69 оказалось слишком медленно.
Хотелось бы оптимизировать без цикла, для определенных значений M,N,
то есть суммой биноминальных коэфициентов.
Здравствуйте, Ароан, Вы писали:
А>Вообще-то и то и другое, но критично именно получить НОМЕР по сочетанию. А>То что предложил Vintik_69 оказалось слишком медленно. А>Хотелось бы оптимизировать без цикла, для определенных значений M,N, А>то есть суммой биноминальных коэфициентов.
Пусть упорядоченный вектор номеров v[0..M), компоненты которого принимают значения [0..N).
Ему можно сопоставить булев вектор флажков f[0..N) где M компонентов взведены (собственно, перестановки).
Естественно, создавать физически этот вектор не будем
Посчитаем, сколько было предшествующих комбинаций: S.
S=0.
Если f[0]==false, то данной комбинации предшествуют все, где f[0]==true и осталось ещё N-1 мест и M-1 флажков: S += C(N-1,M-1).
Переходим к следующему флажку f[1]; N-1 мест и M либо M-1 взведённых флажков...
Значению v[0] соответствуют f[0]...f[v[0]-1]==false и f[v[0]]==true, то есть C(N-1,M-1)+C(N-2,M-1)+...+C(N-v[0],M-1)
Значению v[1] соответствует f[v[0]]...f[v[1]-1]==false и f[v[1]]==true, то есть C(N-v[0]-1,M-2)+...+C(N-v[1],M-2)
И так далее.
То есть, очевидный способ вычисления:
int combi(int n, int m) // найти C(n,m)
{
if(m > n-m) m = n-m; // симметрия, однако!int p=1;
// p = n*(n-1)*...*(n-m-1) / (1*2*...*m)
// p = n/1 * (n-1)/2 * ... * (n-m-1)/mfor(int i=0; i<m; ++i)
{
p *= (n-i);
p /= (i+1);
}
return p;
}
// инкрементные вычисленияint combi_dec_n(int p, int n, int m) // p=C(n,m); найти C(n-1,m)
{
// C(n ,m) = n*(n-1)*...*(n-m-1) / (1*...*m)
// C(n-1,m) = (n-1)*...*(n-m-1)*(n-m) / (1*...*m)return p*(n-m)/n;
}
int combi_dec_m(int p, int n, int m) // p=C(n,m); найти C(n,m-1)
{
// C(n,m ) = n*...*(n-m-2)*(n-m-1) / (1*...*(m-1)*m)
// C(n,m-1) = n*...*(n-m-2) / (1*...*(m-1) )return p*m/(n-m-1);
}
............
int v[M];
int S=0;
int i; // [0..M), индексы vint j; // [0..N), индексы fint p=combi(N,M);
for(i=0; i<M; ++i)
{
int vpred = i==0 ? 0 : v[i-1];
int vnext = v[i];
p = combi_dec_m(p,N-vpred,M-i);
for(j=vpred; j<vnext; ++j)
{
p = combi_dec_n(p,N-j,M-i);
S += p;
}
// и ещё одно место под взведённый флажок
p = combi_dec_n(p,N-vnext,M-i);
}
Вот, вроде бы так.
Что неприятно: у нас цикл получается [0..N)
Увы, я не помню формулу для суммы S(N1,N2,M) = C(N1,M)+...+C(N2,M) и вообще, есть ли она в природе.
Если есть и быстро вычисляется, то можно ускориться
К>Увы, я не помню формулу для суммы S(N1,N2,M) = C(N1,M)+...+C(N2,M) и вообще, есть ли она в природе. К>Если есть и быстро вычисляется, то можно ускориться
Здравствуйте, Ароан, Вы писали:
К>>Увы, я не помню формулу для суммы S(N1,N2,M) = C(N1,M)+...+C(N2,M) и вообще, есть ли она в природе. К>>Если есть и быстро вычисляется, то можно ускориться
А>Свойство треугольника Паскаля: А>S(N1,N2,M) = C(N1,M)+...+C(N2,M) = С(N2+1,M+1)-С(N1+1,M+1)
Не совсем так: при N2==N1 у тебя получается 0, а должен быть C(N1,M)
Наверное, S(N1..N2,M) = C(N2+2,M+1)-C(N1+1,M+1)
индекс f прибавляем
-1+0 true < N+1 -1 > ## в <> написал "сколько осталось позиций до конца f[]". f[-1] - фиктивный флажок, можно считать v[-1]=-1
-1+1 false C(N+1 -2,M-1) |
-1+2 false C(N+1 -3,M-1) |
...... |
v[0]-1 false C(N-v[0]-0,M-1) | S(N-v[0]..N+1 -2,M-1) = C(N+1 -1,M-0)-C(N-v[0],M-0)
v[0] true < N-v[0]-1 >
v[0]+1 false C(N-v[0]-2,M-2) |
v[0]+2 false C(N-v[0]-3,M-2) |
...... |
v[1]-1 false C(N-v[1]-0,M-2) | S(N-v[1]..N-v[0]-2,M-2) = C(N-v[0]-1,M-1)-C(N-v[1],M-1)
v[1] true < N-v[1]-1 >
То есть, для каждого i из [0..M) нужно S += C(N-v[i-1]-1,M-i)-C(N-v[i],M-i)
Вроде бы, ничего не перепутал?
Все биномиальные коэффициенты здесь можно посчитать инкрементно.
Здравствуйте, Кодт, Вы писали:
К>То есть, для каждого i из [0..M) нужно S += C(N-v[i-1]-1,M-i)-C(N-v[i],M-i)
Вот такой алгоритм выдает правильный результат, но соседние элементы судя по всему можно свести к одному C,
то есть всего в алгоритме будет M+1 биноминальных коэфициентов.
int combination_index(int *v, int m, int n)
{
int s = 0, v0 = 0, v1;
for(int i=0; i<m; i++)
{
v1 = v[i];
s += combination(m-i, n-v0) - combination(m-i, n-v1);
v0 = v1+1;
}
return s;
}
Перекуём баги на фичи!
