VPF::Задача про вложения - Форум программистов

Stream

Дата 29.10.2005, 14:02 (ссылка)

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

Загрузка ...

Новичок

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

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

Помогите разобраться с задачей. (реализация на С) smile

Перечислить все вложения (функции, переводящие раз-
ные элементы в разные) множества {1..k} в {1..n} (предполагает-
ся, что k <= n). Порождение очередного элемента должно требовать
порядка k действий.

Mad

Дата 30.10.2005, 11:53 (ссылка)

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

Загрузка ...

Опытный

Профиль
Группа: Эксперт
Сообщений: 656
Регистрация: 18.10.2004
Где: Одесса

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

Stream
Тебе нужун алгоритм, или готовый код ? smile

Если кодЮ тогда сначало сделай сам (как получиться) а потом поможем исправить ошибки, а вот полностью решать за тебя задачу .... smile

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

Stream

Дата 31.10.2005, 17:53 (ссылка)

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

Загрузка ...

Новичок

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

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

У меня проблема в нахождении количества перестановок множества {1..n}
Искал в инете, но на С ничего не нашёл, а переписать с другого языка никак не получается smile

Добавлено @ 17:55
В смысле сама реализация, а то, что количество перестановок n! - я знаю

yaja

Дата 31.10.2005, 21:27 (ссылка)

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

Загрузка ...

Шустрый

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

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

Я правильно понял, что тебе нужны все перестановки n элементов

Код


#include <stdio.h>

inline void swap(char& a, char& b) {
  char tmp = a; a = b; b = tmp;
}
inline void swap(short& a, short& b) {
  short tmp = a; a = b; b = tmp;
}

char p[15];
short d[15], _p[15];


int main() {
  int n;
  freopen("perm.in", "r", stdin);
  freopen("perm.out", "w", stdout);

  scanf("%i", &n);

  for (int i = 0; i < n + 2; i++) {
    p[i] = '0' + i;
    _p[i] = i;
    d[i] = -1;
  }
  d[1] = 0;
  int m = _p[0] = n + 1;
  p[0] = '0' + n + 1;

  while (m != 1) {
    p[n + 1] = 0;
    printf("%s\n", &p[1]);
    p[n + 1] = '0' + n + 1;

    m = n;
    while (p[_p[m] + d[m]] > m + '0') {
      d[m] = -d[m];
      m--;
    }

    swap(p[_p[m]], p[_p[m] + d[m]]);
    swap(_p[p[_p[m]] - '0'], _p[m]);
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}

Читай любую книгу по комбинаторике, или rain.ifmo.ru/cat
Если тебе нужны не перестановки, а размещения без повторений, то генерятся они подобным же образом, как и сочетания, легко переделать smile

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