Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [C++] инъективные отображения

Автор: Yellow666 28.6.2009, 13:34

Помогите пожалуйста решить задачу,или подскажите алгоритм! найти все инъективные отображения из множества чисел {1,2,...,n} в множество чисел {1,2,...,m}, где n<=m.

Автор: zim22 28.6.2009, 13:41

Цитата(Yellow666 @ 28.6.2009, 13:34

)

найти все инъективные отображения из множества чисел

что это такое? приведите пример

Автор: Yellow666 29.6.2009, 10:02

например: первое множество {1,2,3} ,второе {1,2,3}

1->1  1->2  1->1  1->2  1->3  1->3
2->2  2->1  2->3  2->3  2->1  2->2
3->3  3->3  3->2  3->1  3->2  3->1

всего их m!;

Автор: zim22 29.6.2009, 12:00

Цитата(Yellow666 @ 29.6.2009, 10:02

)

например: первое множество {1,2,3} ,второе {1,2,3}

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

какой будет результат, если у нас два множества разных размеров?
первое: {1, 2, 3}
второе: {1, 2, 3, 4, 5}

Автор: kamre 29.6.2009, 13:56

Цитата(zim22 @ 29.6.2009, 12:00)

какой будет результат, если у нас два множества разных размеров?
первое: {1, 2, 3}
второе: {1, 2, 3, 4, 5}

Выбираются три элемента из второго множества, и они сопоставляются элементам из первого множества.
Например вот так: выбираем (3, 4, 5), здесь важен порядок, и сопоставляем { 1 -> 3, 2 -> 4, 3 -> 5 } Всего таких отображений будет 5*4*3=60.

Автор: Yellow666 29.6.2009, 14:09

Цитата(zim22 @ 29.6.2009, 12:00

)

результат для каждой пары чисел будет их сумма

что это значит?для какой пары чисел?
мне надо как-то запрогить всевозмжное число перестановок (всего m!) и какждый раз,при получении перестановки из m-множества, n первых элементов из нее сопоставить с элементами n-множества.

Автор: zim22 29.6.2009, 16:16

Цитата(Yellow666 @ 29.6.2009, 14:09

)

мне надо как-то запрогить всевозмжное число перестановок

<algorithm>
std::next_permutation - следующая перестановка
std::prev_permutation - предыдущая перестановка

Цитата(Yellow666 @ 29.6.2009, 14:09

)

что это значит?для какой пары чисел?

я не знаю, что такое инъективное отображение. поэтому и попросил пример.

а судя по вашему примеру у вас было два множества. и вы "как-то" получили третье.
как мне догадаться как вы его получили? smile

если складывать число в позиции 0 < i < n из первого множества с числом из второго множества, то получается третье множество! smile

1 множество) 1->1  1->2  1->1  1->2  1->3  1->3
2 множество) 2->2  2->1  2->3  2->3  2->1  2->2
3 множество) 3->3  3->3  3->2  3->1  3->2  3->1

Автор: kamre 30.6.2009, 14:23

Цитата(zim22 @ 29.6.2009, 16:16)

я не знаю, что такое инъективное отображение. поэтому и попросил пример.

Это такое отображение, которое разные элементы переводит в разные, т.е. (x != y) => (f(x) != f(y)). Поэтому нужно из второго множества выбрать столько же элементов, сколько и в первом, и их сопоставить.

Автор: airyashov 1.7.2009, 13:19

если правильно понял задачу

Код


#include <iostream.h>
#include <conio.h>

#define cM1 3
#define cM2 5

int M1[cM1]={1,2,3};
int M2[cM2]={1,2,3,4,5};
int flag[cM2],i;
int depth=0;

void Do(void){
 int j;
    if(depth==cM1){
    //result;
        for(j=0;j<cM2;j++)
            if(flag[j]!=0){
                i=flag[j]-1;
                cout<<M1[i]<<"->"<<M2[j]<<" ";
            }
        cout<<endl;
    }
    else{
        for(j=0;j<cM2;j++)
            if(flag[j]==0){
                depth++;
                flag[j]=depth;
                Do();
                depth--;
                flag[j]=0;
            }
    }
}


int main(void){
//zero flags
for(i=0;i<cM2;i++) flag[i]=0;
clrscr();
Do();

return 0;
}