Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 23.01.2010, 16:15
Eugene86

 
Сообщений: n/a

Перестановки
На сайте нашёл статью http://algolist.manual.ru/maths/comb...rmutations.php
про перестановки(рекурсивный алгоритм).
Работает так. Вводим два числа: 1, 2.
Перестановки выглядят так: 12, 21.
Объясните как сделать так: если вводятся одинаковые числа - по ним перестановки не будет, т.е. вводим: 1, 1.
На выходе только :11.
  #2  
Старый 23.01.2010, 17:28
гость

 
Сообщений: n/a

std::next_permutation используем.
  #3  
Старый 23.01.2010, 17:40
Eugene86

 
Сообщений: n/a

А без неё как?
  #4  
Старый 23.01.2010, 18:27
гость

 
Сообщений: n/a

на каждом шаге рекурсии из каждой группы одинаковых чисел бери только одно число (любое, первое например)
  #5  
Старый 23.01.2010, 20:07
Новичок

Отправить личное сообщение для Eugene86 Посмотреть профиль Найти все сообщения от Eugene86
 
Регистрация: 23.01.2010
Сообщений: 1

Сообщение от гость Посмотреть сообщение
на каждом шаге рекурсии из каждой группы одинаковых чисел бери только одно число (любое, первое например)
Код:
program PerestanovkiRecursion;
	  type Pere=array [byte] of integer;
	  var N,i,j:integer;
	      X:Pere;
	  procedure Generate(k:integer);
	    var i,j:byte;
	    procedure Swap(var a,b:integer);
	      var c:integer;
	    begin c:=a;a:=b;b:=c end;
	  begin
	    if k=N then
	      begin for i:=1 to N do write(X[i]);writeln end
	    else
	      for j:=k+1 to N do
		begin

     if ((k+1)<>(j))and((x[k+1])=(x[j])) then continue;
 	  Swap(X[k+1],X[j]);
	   Generate(k+1);
		  Swap(X[k+1],X[j])
		end
	  end;
	begin
	  write('N=');readln(N);
    X[1]:=1;X[2]:=1; X[3]:=0;x[4]:=0;
	  { for i:=1 to N do X[i]:=i;}
	  Generate(0);
    readln;
	end.
Я правильно понял?
  #6  
Старый 23.01.2010, 20:36
гость

 
Сообщений: n/a

ну вообще-то нет.

я имел в виду что-то вроде этого:
Код:
#!/usr/bin/env python
# coding: utf-8

def permutations(objects):
    N = len(objects)
    objects = sorted(objects)
    res = []
    used = [False] * N

    def go(i):
        if i == N:
            print res
        else:
            for j in range(N):
                if used[j]: continue
                if j > 0 and not used[j-1] and objects[j-1] == objects[j]:
                    # <- вот ключевой момент: игнорируем повторяющиеся элементы,
                    #  из группы одинаковых элементов (расположенных рядом, т.к. предварительно отсортировали все)
                    #  пропускаем все кроме первого неиспользуемого элемента.
                    continue
                res.append(objects[j])
                used[j] = True
                go(i+1)
                used[j] = False
                res.pop()

    go(0)

permutations([1,1,0,0])
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Перестановки гость Математические алгоритмы (другое) 2 16.04.2008 21:18
Комбинаторика. Перестановки гость Математические алгоритмы (другое) 6 16.04.2008 20:16