Поиск подмножества

[Lodyr]

Доброго времени суток!
Помогите с решением задачи:
Найти в массиве натуральных чисел самое большое подмножество элементов, в котором любые два элемента имеют одинаковое множество простых делителей.

#include <iostream>
#include <cmath>
using namespace std;

bool isSimple(int a)
{for (int i=2; i<=a/2; ++i)
    {
        if (a%i==0) return false;
    }
return true;
}

bool isProst(int a)
{short r; int d;
if (a<2) return false;
else if (a==2) return true;
else if (a%2==0) return false;
else
{
    r=sqrt(a);
    d=3;
    while ((a%d!=0)&&(d<=r)) {d=d+2;}
    if (d>r) return true;
    else return false;
}
}

int NOD (int a,int b)
{while (a!=0 && b!=0)
{
    if (a>=b) a=a%b;
    else b=b%a;
}
return a+b;
}

int main()
{int a,j,n,l,p,h,i,mas1[10],mas2[10],mas3[10],t,k;
cout<<"vvedite n"<<endl;
cin>>n; k=0;
for (j=1; j<=n; j++)
{cout<<"vvedite"<<" "<<j<<" "<<"element"<<endl; cin>>a;
t=0;
for (i=1; i<=a/2; ++i)
{
    if (a%i==0 && isSimple(i))
    {cout<<i<<" "; t=t+1;}
}
if (isProst(a)==true)
{cout<<a; t=t+1;}
mas1[k]=a; mas2[k]=t; k=k+1;
cout<<endl;
}
cout<<endl;
for (k=0; k<n; ++k)
{
    cout<<mas1[k]<<" ";
}
cout<<endl;
for (k=0; k<n; ++k)
{
    cout<<mas2[k]<<" ";
}
cout<<endl;
for (int i=n-1; i>0; i--)
for (int j=0; j<i; j++)
if (mas2[j]>mas2[j+1])
{
    swap(mas2[j], mas2[j+1]);
    swap(mas1[j], mas1[j+1]);
}
for (k=0; k<n; k++)
{
    cout<<mas1[k]<<" ";
}
cout<<endl;
for (k=0; k<n; k++)
{
    cout<<mas2[k]<<" ";
}
cout<<endl;
p=0; h=0;
for (l=0; l<n; l++)
{
if (((mas2[l]==mas2[l+1]) && (NOD(mas1[l],mas1[l+1])==mas1[l])) || ((mas2[l]==mas2[l+1]) && (NOD(mas1[l],mas1[l+1])==mas1[l+1])))
{mas3[p]=mas1[l];
mas3[p+1]=mas1[l+1];
p=p+1;}
if ((mas2[l]=mas2[l+1]) && (NOD(mas1[l],mas1[l+1])!=mas1[l]));
if ((mas2[l]=mas2[l+1]) && (NOD(mas1[l],mas1[l+1])!=mas1[l+1]));
}
h=p+1;
for (p=0; p<h; p++)
{
cout<<mas3[p]<<" ";
}
return 0;
}

проблема состоит в поиске этого самого подмножества, если я введу такие числа
5 25 125 678 12
то в конце правильно выводит 5 25 и 125
но вот если 5 12 45 55 144 = выдать должен 12 и 144 а так выдает заковырестое число...
Многие советуют алгоритм перебора всех сочетаний = можно узнать про него?

[LeBron]

Найти для каждого числа количество простых делителей, и взять все числа с тем количеством, которое встречается больше всего раз. Тогда сложность будет порядка О(N*maxN^(1/3)), а не О(2^N), как при переборе сочетаний (если правильно понял относительно сочетаний, то эта идея "подвиснет" уже при 25 числах, а при 50 числах не выполнится и за год)...

[Lodyr]

а что если у нас в массиве каждое число имеет одинаковое количество простых делителей
например
45 55 15 135
3 3 3 3
должен выдать 45 55 135
и что делать в таком случае?

[LeBron]

Сообщение от Lodyr

а что если у нас в массиве каждое число имеет одинаковое количество простых делителей
например
45 55 15 135
3 3 3 3
должен выдать 45 55 135
и что делать в таком случае?

А... Извините... Я невнимательно прочел, думал, что одинаковое за мощностью, т.е. одинаковое количество простых множителей в факторизации...
Тогда действительно перебор сочетаний - самый очевидный вариант. Не факт, что самый быстрый, но быстрее с ходу не придумать.
Суть перебора - просматриваем все числа от 1 до 2^N-1, и для каждого числа формируем проверяемый набор за таким принципом: если в числе на итой позиции в двоичной записи единица, то берем итый элемент, иначе - не берем. Проверяем набор, если подходит - значит подходит, иначе - не судьба. Среди всех подходящих выбираем максимальный.

[LeBron]

Можно быстрее, придумал)
Можно "сливать в блоки"...
Берем первое число... Ищем все "подходящие". Если числа подходят к первому, то они подходят и между собой (если я правильно понял задание). Получаем максимальный набор с первым числом. Далее аналогично для остальных. Сложность такая же, как в моем первом варианте - О(N*maxN^(1/3)), если предположить, что числа достаточно большие относительно их количества.

[Lodyr]

а можно посмотреть как это все будет выглядеть в коде?
вы предлогаете сравнивать 1 со всеми последующими = найдем все подходящие = сформируем первое стартовое множество = вдруг остальные комбинации не подойдут... а дальше то как делать?
посмотрел тут варианты = для трех элементов нужно 5 сравнений, для 4 более 15...
у меня такое предложение =
если у меня два элемента с одинаковым множеством стоят рядом = то не проблема = все находит
пусть даны числа 5 12 15 30 60
для них кол-во прост делит 2 3 3 4 4
берем первыую пару 2 и 3 = они неравны = идем дальше, 3 и 3= одинаковы ищем НОД(12 и 15) если он неравен ни одному из чисел (ни 12 и ни 15) - то и их множества разные, соответственно наоборот если равен 12 или 15 - то точняк множества одинаковы и их берем за наше подмножество
но в нашем случае это не так поэтому переходим к следующей паре
потом дальше 3 и 4 = неравны берем другую пару
4 и 4 = подходит НОД (30 и 60) = 30 = значит их множества одинаковы = берем их за наше подмножество и все олрайт =)
следующую пару ведь уже не можем взять значит на выходе 30 и 60
Но ведь нужна универсальная формула....

[LeBron]

Сообщение от Lodyr

а можно посмотреть как это все будет выглядеть в коде?
вы предлогаете сравнивать 1 со всеми последующими = найдем все подходящие = сформируем первое стартовое множество = вдруг остальные комбинации не подойдут... а дальше то как делать?
посмотрел тут варианты = для трех элементов нужно 5 сравнений, для 4 более 15...

Количество сравнений между элементами будет всего порядка N^2. Ну и еще множители сравнивать... Но если хэш-функцию сделать, то вообще можно считать, что условно это квадрат.
Для 20 чисел условно 400 (на самом деле даже 200) сравнений. А если полный перебор сочетаний, то для 20 чисел будет более миллиона сравнений.
Прикол с НОД не совсем катит. Допустим, есть числа 18 и 12. Их множества простых делителей одинаковые (2,3). Но НОК не равно ни 18, ни 12.

[Lodyr]

Тогда я просто не представляю как их можно сравнивать...
вся работа только на смарку

[LeBron]

Сообщение от Lodyr

Тогда я просто не представляю как их можно сравнивать...
вся работа только на смарку

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

[Lodyr]

Я правильно поинмаю вашу идею?

#include <iostream>
#include <cmath>
using namespace std;

bool isSimple(int a)
{for (int i=2; i<=a/2; ++i)
    {
        if (a%i==0) return false;
    }
return true;
}

bool isProst(int a)
{short r; int d;
if (a<2) return false;
else if (a==2) return true;
else if (a%2==0) return false;
else
{
    r=sqrt(a);
    d=3;
    while ((a%d!=0)&&(d<=r)) {d=d+2;}
    if (d>r) return true;
    else return false;
}
}

int main()
{int a,j,p,n,i,k,t;
double matrix[10][10];
cout<<"vvedite n"<<endl;
cin>>n;
for (k=0; k<n; k++)
for (p=0; p<n; p++)
{
    matrix[k][p]=0;
}
k=0;
for (j=1; j<=n; j++)
{cout<<"vvedite"<<" "<<j<<" "<<"element"<<endl; cin>>a;
t=0; matrix[k][t]=a;
for (i=1; i<=a/2; ++i)
{
    if (a%i==0 && isSimple(i))
    {cout<<i<<" "; t=t+1; matrix[k][t]=i;}
}
if (isProst(a)==true)
{cout<<a; t=t+1; matrix[k][t]=a;}
k=k+1;
cout<<endl;
}
for (k=0; k<n; ++k)
{
for (t=0; t<n; ++t)
cout<<matrix[k][t]<<" ";
cout<<endl;
}
return 0;
}

Поясню в первом столбце у нас будут храниться сами элементы, а в каждой строке напротив первого столбца = их простые делители причем уже отсортированные по возрастанию, если у нас незаполнены ячейки матрицы = то их забиваем нулями.
Например
6 элементов
5 1 5 0 0 0
12 1 2 3 0 0
18 1 2 3 0 0
25 1 5 0 0 0
6 1 2 3 0 0
10 1 2 5 0 0