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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 24.05.2007, 19:40
Bard

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

задача на строки
Ребята помогите решить задачку на строку.
Задаеться строка S. Требуеться найти ее порядковый номер в лексографическом порядке всех строк из того же набора букв.
Например строка "abba" третья среди строк "aabb","abab","abba","baab","baba","bbaa".

Помогите чем можете время поджимает...
  #2  
Старый 24.05.2007, 21:12
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

а ты умеешь находить номер в лекс. порядке для данной перестановки набора N чисел 0.. N-1?

твоя задача сводится к аналогичной, но для мультисета, для него будет несколько сложнее, видимо.
  #3  
Старый 24.05.2007, 22:15
bard

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

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


большое спс
  #4  
Старый 25.05.2007, 06:18
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Код:
function PermNum(A: array of Byte): Integer;
var
  N, i, j, Fact: Integer;
begin
  N := Length(A);
  Fact := 1;
  for i := 2 to N do
    Fact := Fact * i;
  Result := 1;
  for i := 0 to N - 1 do begin
    Fact := Fact div (N - i);
    Result := Result + A[i] * Fact;
    for j := i + 1 to N - 1 do
      if A[j] > A[i] then
        Dec(A[j]);
  end;
end;

procedure TForm27.Button11Click(Sender: TObject);
begin
  Caption := IntToStr(PermNum([3, 0, 1, 2]));
end;
  #5  
Старый 25.05.2007, 13:10
bard

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

но мне же нужен строчный тип а у тебя целый...
пожалуйста напиши мне код задачи я тебе буду очень благодарен
  #6  
Старый 25.05.2007, 14:12
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>но мне же нужен строчный тип а у тебя целый
сортируешь свою строку по неубыванию, и переводишь в целый тип

пример: 'babaca' -> 'aaabbc'-> [0,0,0,1,1,2] массив байтов
это мультимножество (MultiSet) с сигнатурой {3,2,1} (три одинаковых первых элемента, два вторых, один третий)

>пожалуйста напиши мне код задачи
Нет у меня времени разбираться.

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

А для мультимножества с сигнатурой {n1, n2, ... nk}, где Sum(ni) = N, перестановок будет N!/(П((ni)!)) (П - произведение)
Вот и попробуй сгенерировать перестановки для разных наборов, и
понять закономерности.

Последний раз редактировалось MBo, 25.05.2007 в 14:51.
  #7  
Старый 25.05.2007, 16:21
bard

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

да но ведь обычная перестановка(тоесть пермутация) это не то же что и лексографический(алфавитн й) порядок...
  #8  
Старый 25.05.2007, 16:41
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

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

Понятие "лексографический порядок" применяется к порядку генерации перестановок. Пример лексикографического порядка для трех элементов с номером перестановки:
1: 0 1 2
2: 0 2 1
3: 1 0 2
4: 1 2 0
5: 2 0 1
6: 2 1 0

Кроме лексикографического (i-я строка меньше i+1 -ой) существует множество других порядков(антилекс, колекс, minimal-change и т.д.)

Те же перестановки в minimal-change порядке
1: 0 1 2
2: 0 2 1
3: 2 0 1
4: 2 1 0
5: 1 2 0
6: 1 0 2

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

Последний раз редактировалось MBo, 25.05.2007 в 16:45.
  #9  
Старый 25.05.2007, 16:56
bard

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

можешь написать мне тот же код только на пакале а то я в делфи не очень...
  #10  
Старый 25.05.2007, 17:55
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

еще раз - этот код - для перестановок набора без повторов символов, тебе он не подойдет, а дан как толчок к размышлению

P.s. код функции в дельфи и паскале наряд ли будет
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задачка на строки NeiroN Задачи 2 31.05.2007 04:38