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

Yellow666

Дата 28.6.2009, 13:34 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 28.6.2009

Репутация: нет
Всего: нет

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

zim22

Дата 28.6.2009, 13:41 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69

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

)

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

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

--------------------

C++ FAQ Lite

Yellow666

Дата 29.6.2009, 10:02 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 28.6.2009

Репутация: нет
Всего: нет

например: первое множество {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 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69

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

)

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

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

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

--------------------

C++ FAQ Lite

kamre

Дата 29.6.2009, 13:56 (ссылка)

(голосов:1)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 330
Регистрация: 24.3.2006

Репутация: 2
Всего: 13

Цитата(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 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 28.6.2009

Репутация: нет
Всего: нет

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

)

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

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

zim22

Дата 29.6.2009, 16:16 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 16
Всего: 69

Цитата(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

Это сообщение отредактировал(а) zim22 - 29.6.2009, 16:18

--------------------

C++ FAQ Lite

kamre

Дата 30.6.2009, 14:23 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 330
Регистрация: 24.3.2006

Репутация: 2
Всего: 13

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

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

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

airyashov

Дата 1.7.2009, 13:19 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 284
Регистрация: 1.7.2008

Репутация: 1
Всего: 6

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

Код


#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;
}

Это сообщение отредактировал(а) airyashov - 1.7.2009, 13:37

--------------------

icq:3(один)7748666
mail:airyashov( а )inbox.ru

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »