Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 14:48

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: *найти все возможные комбинации букв внутри строки
СообщениеДобавлено: Вт янв 22, 2008 00:54 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
<dd>Перечислить все возможные комбинации букв, которые можно получить из исходной строки текста и вывести их на экран. Например, для варианта из двух символов должно быть выдано два значения: S" ab" variants > ab ba, для трех символов таких вариантов будет уже шесть: S" abc" variants > abc acb cba bca bac cab. Кроме того, если в исходной строке есть одинаковые символы, то повторяющиеся в результате преобразования комбинации должны быть исключены из результата: S" aab" variants > aab aba baa - остальные варианты должны быть исключены.
<dd> Строка состоит из однобайтных символов. Ограничения на тип символов нет, то есть на входе может быть строка cодержащая пробелы, переводы строки, другие однобайтовые спец символы. Ограничение по длине входной строки 10 символов(то есть от 0 до 10).
<pre>
\ на входе адрес строки со счетчиком, содержащим исходную строку
\ на выходе число n - количество полученных вариантов перестановки
\ на экран(в stdout) выводится список полученных вариантов.
: variants ( asc # --> n )

;
</pre>

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Последний раз редактировалось mOleg Чт мар 20, 2008 16:43, всего редактировалось 1 раз.

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт янв 22, 2008 06:48 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
mOleg писал(а):
Ограничение по длине входной строки 10 символов(то есть от 0 до 10)


от 0 до 10 - это, вообще говоря, 11 символов, или я снова чего-то туплю?

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт янв 22, 2008 06:55 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
WingLion писал(а):
от 0 до 10 - это, вообще говоря, 11 символов, или я снова чего-то туплю?

8) на самом деле 0 - это пустая строка, а 10 символов- самая длинная.

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт янв 22, 2008 11:16 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Это реальная задача или только на конкурс?

Это можно сделать на бэкфорте, смоделировав функции Пролога, пару строчек получится.
Но бэкфорт я никак не освою

алгоритм таков -
создаём комбинации букв вложенными перестановками
наподобие того, как есть
a b c d
сначала оставляем а на первом месте, при этом присоединяем к нему все возможные комибнации "хвоста" строки :
b c d, что в свою очередь достигается делением строки на голову - b и хвост...
потом меняем а с b и проделываем ту же операцию с b a c d, затем а с c . Делая это, мне кажется, достаточно пропускать перестановки, если буквы одинаковы, то есть не менять местами
Хотя нет, тут зависимость более сложная - одинаковые комбинации могут получиться более сложным путём.
Факториал 10 = 3628800
В принципе можно организовать минибазуданных с быстрым поиском, в память она должна вместиться :) и сравнивать каждую новую строку.
Но это неэкономно ...
тогда достаточно просчитывать некую "контрольную сумму" строки, и если таковая совпадает, строку пропускаем. Контрольная сумма, в зависимости от числа допустимых знаков, может оказаться "длинным" числом, так что может понадобится библиотека работы с длинными числами, впрочем, и тут есть решение: нужно вычислять такую сумму только для тех случаев, когда одинаковые комбинации из равных символов образуются более сложным образом, чем простой заменой а и а. Это может получиться только в том случае, если есть более одной пары одинаковых символов

скажем с строке 1 1 3 4 5 2 2
комбинация 2 2 3 4 5 1 1
может получиться заменой первой единицы на последнюю двойку и второй единицы на предпоследнюю двойку, а может вторая двойка меняться на последнюю, а первая - на предпоследнюю и это нельзя (особенно в более сложных случаях) отследить с помощью правила "не менять а и а".

Тогда алгоритм состоял бы из
1. читаем строку, определяем, какие символы в ней повторяются, таковым присваиваем номера (от 0 до 7 :D 8) ) - для контрольной суммы
2. осуществляем перестановки, определяя для каждой контрольную сумму только для указанных чисел, тогда нам не понадобится работа с длинными числами
3. встретив комбинацию с неподходящей контрольной сумой, таковую выбраковываем, выбраковка происходит, когда "перемещено" последнее из чисел, имеющих пару

причём контрольная сумма в этом случае состояла бы из 2 чисел - 1 число - это "сумма" по положению - т.е.
скажем строка 1113345678 должна давать сумму по положению первых пяти знаков
и 2 число - это сумма по способу получения

это значит, что если строка 1113345678 получена из 1114567833
то должны различаться вторые числа контролльных сумм для
1113345678 и 1113345678
а первые должны совпасть

тогда вариант(ы) должен(ы) выбраковываться, если та же сумма по положению которая уже встречалась, соответствует другой сумме по перемещению, что соответствует случаю "та же комбинация получена другим путём"

Это если говорить о экономности.
Но если о простоте, то должен быть другой более простой алгоритм - например, чтобы не считать контрольные суммы, можно сначала выявить одинаковые символы, получить все допустимые их комбинации
из ААОО
получить

АОАО
ОАОА
АООА
ОААО
затем расположить оставшиеся символы вокруг и между этими всеми возможными способми
т.е. если в строке 6 символов, мы получаем строки
_ _ АОАО
_ А_ОАО
_ АО_АО и т.д.
и на места пустые располагаем оставшиеся буквы
тут сразу понятно число комбинаций - каждой допустимой комбинации из символов имеющих пару соответствуют все комбинаци из символов без пары во всех положениях - произведение 3 чисел

:( может есть что и попроще, и даже такое, что я должен помнить, но вот что-то не вспомню ...

_________________
понимаю некоторую бестолковость некоторых вопросов


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср янв 23, 2008 02:05 
Код:
CREATE SYMS 256 ALLOT

CREATE CODE  10 ALLOT
CREATE COUNT 10 ALLOT
CREATE Str 10 ALLOT
VARIABLE Всего
VARIABLE Длина
VARIABLE Вариантов

: StrLen \ ( addr --> len )
-1
BEGIN
  1+
  OVER OVER + C@ 0 =
UNTIL
SWAP DROP
;

: Очистить \ ( num addr --> )
SWAP OVER + SWAP DO
  0 I C!
LOOP
;

: Scan \ ( addr --> )
256 SYMS Очистить

Длина @ 0 DO
  DUP I + C@ SYMS + DUP C@ 1+ SWAP C!
LOOP
DROP
;

: Compress
0 Всего !
256 0 DO
  SYMS I + C@ IF
   I CODE Всего @ + C!
   SYMS I + C@ COUNT Всего @ + C!
   Всего @ 1+ Всего !
  THEN
LOOP
;

: ClearStr
10 0 DO
  0 Str I + C!
LOOP
;

: Print
Str PRINT CR
;

: Recurs \ (i глубина --> )
OVER
  CODE + C@
  OVER Str + C!

OVER COUNT + DUP C@ 1- SWAP C!

DUP Длина @ 1- = IF
  Print
  Вариантов @ 1+ Вариантов !
ELSE
  Всего @ 0 DO
   COUNT I + C@ IF
    I OVER 1+ Recurs
   THEN
  LOOP
THEN

OVER COUNT + DUP C@ 1+ SWAP C!

DROP DROP
;

: variants \ ( asc# --> n )
DUP StrLen Длина !

Длина @ 0 = IF 0
ELSE

  CLS 0 0 GOTOXY
  Scan Compress
  ClearStr
  0 Вариантов !
  Всего @ 0 DO
   I 0 Recurs
  LOOP

  Вариантов @
THEN
;


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 24, 2008 16:29 
Не в сети
Аватара пользователя

Зарегистрирован: Вт сен 11, 2007 11:07
Сообщения: 187
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
запускать так:
G:\007\2\spf419\spf4.exe <source_file

проверять так:
G:\007\2\spf419\spf4.exe <source_file | grep ">" | sort | uniq | wc

предполагается, что на машине есть цигвин, помимо прочих утилит

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

Код:
\ -----------------------------------------------------------------------------
\   Sequence Permutation Generator (C) Thu 24 Jan 14:24:23 2008
\ -----------------------------------------------------------------------------
: (cswap) ( a1 a2 --> )
    2DUP 2>R C@ SWAP C@ R> C! R> C!
;

\ -----------------------------------------------------------------------------
: (cnotfind) ( c s2 s1 --> t/f )
    1 -ROT ?DO OVER I C@ = IF 0 AND LEAVE THEN LOOP
    SWAP DROP
;

\ -----------------------------------------------------------------------------
: (variants) ( 0 s2 s1 str len --> count s2 s1' str len )

    2>R 2DUP - 1 < IF
        2>R 1+ 2R>
        ." > " 2R> 2DUP TYPE CR
        EXIT
    THEN

    DUP >R BEGIN 2DUP > WHILE

        DUP C@ OVER R@ (cnotfind) IF

            DUP R@ (cswap)

            R> 1+ SWAP 2R> ROT >R
            RECURSE
            R> -ROT 2>R SWAP 1- >R

            DUP R@ (cswap)
        THEN

    1+
    REPEAT DROP R> 2R>
;

\ -----------------------------------------------------------------------------
: variants ( asc # --> n )
    DUP 0 = IF 2DROP 0 EXIT THEN

    2DUP 2>R OVER + SWAP 0 -ROT 2R> (variants) 2DROP 2DROP
;

\ -----------------------------------------------------------------------------
S" aabcaaa" 2DUP variants .( ] variants: ) . TYPE CR CR
\ S" aabb" 2DUP variants .( ] variants: ) . TYPE CR
\ S" abababab" 2DUP variants .( ] variants: ) . TYPE CR
\ S" abc" 2DUP variants .( ] variants: ) . TYPE CR


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 24, 2008 18:41 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
garbler писал(а):
to вопрос: как-то всё у тебя сложно написано,

Вот так с ходу не подумав сложно и получается :(
garbler писал(а):
пролог и бэкфорт
тут избыточны, вернее, они очень пригодятся, если надо сериализовать
действия по использованию получившихся строк (а не просто их (строки)
сдампить куда-то)
Я вообще-то там спрашиваю - нужны эти строки потом или просто так задача ...

_________________
понимаю некоторую бестолковость некоторых вопросов


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 24, 2008 19:51 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
garbler
8) спасибо за участие, но ваш код не полностью соответствует ТЗ 8( надо бы отсеивать уже встреченные комбинации.
ничего, если я немного прокоментирую ваш код?

вопрос писал(а):
Вот так с ходу не подумав сложно и получается

это потому что задачку надо решать, а не рассуждать о ее решении, но всеравно спасибо за участие! ;)

вопрос писал(а):
Я вообще-то там спрашиваю - нужны эти строки потом или просто так задача ...

Вообще, задачка классическая - у меня встречалась на втором курсе в каком-то из заданий.
строки, вероятно нужны, но в ТЗ нужно вернуть лишь количество различных возможных перестановок, а сами перестановки на экран отобразить.
например, для такой последовательности: s" 100000001" variants CR .
количество вариантов влезет на один экран ;)

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 24, 2008 20:58 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Оно и отсеивает, насколько я успел понять - если не ошибся - с помощью порядка перебора -
взаимное расположение одинаковых символов не меняется, меняется только их положение и расстояние между ними, за счёт этого исключено "перекрёстное" получение из aabb bbaa

но алгоритм всё равно рекурсивный (конец строки - на самом деле начало)
Другое дело - я бы потребовал доказательство, не отсеиваются ли при этом "законные" строки, т.к. не всё меняется со всем

_________________
понимаю некоторую бестолковость некоторых вопросов


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 24, 2008 21:06 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
вопрос писал(а):
Оно и отсеивает, насколько я успел понять - если не ошибся - с помощью порядка перебора -
взаимное расположение одинаковых символов не меняется, меняется только их положение и расстояние между ними, за счёт этого исключено "перекрёстное" получение из aabb bbaa

да, верно 8)
жаль, что коментариев нет 8(

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 24, 2008 21:25 
Не в сети
Аватара пользователя

Зарегистрирован: Вт сен 11, 2007 11:07
Сообщения: 187
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
вопрос писал(а):
Я вообще-то там спрашиваю - нужны эти строки потом или просто так задача ...


угу.... и, как видишь, с этим я вовсе даже не спорил :-)

думаю, алгоритм будет несколько виднее на прологе/перле, их и прицеплю:
for: Turbo Prolog v2.0 by Borland Intl.
for Perl


Последний раз редактировалось garbler Чт янв 24, 2008 21:53, всего редактировалось 1 раз.

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 24, 2008 21:37 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
garbler писал(а):
думаю, алгоритм будет несколько виднее на прологе/перле, их и прицеплю:

обратите пожалуйтса внимание на правила конкурса пункт 5.
дайте пожалуйста ссылку на код (если надо, могу разместить у себя).

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 24, 2008 21:40 
Не в сети
Аватара пользователя

Зарегистрирован: Вт сен 11, 2007 11:07
Сообщения: 187
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
mOleg писал(а):
garbler
8) спасибо за участие, но ваш код не полностью соответствует ТЗ 8( надо бы отсеивать уже встреченные комбинации.

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

для того, чтобы ещё лучше увидеть разницу, рекомендую воспользоваться такой
версией (cnotfind)

Код:
: (cnotfind) ( c s2 s1 --> t/f ) 2DROP DROP 1 ;


так мы получим полный перебор без учёта "дублей" символов, входящих в строку

mOleg писал(а):
ничего, если я немного прокоментирую ваш код?

с удовольствием, буду только рад

mOleg писал(а):
например, для такой последовательности: s" 100000001" variants CR .
количество вариантов влезет на один экран ;)

для 80х25 не влезет, ибо 36 комбинаций

p.s.
mOleg писал(а):
дайте пожалуйста ссылку на код

постоянного сайта у меня нет (безалаберность)

mOleg писал(а):
(если надо, могу разместить у себя).

было-бы неплохо.... если можно.

или, может, лучше, для таких случаев раздел-(файло/исходнико)помойку
на форуме создать?


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 24, 2008 22:21 
Не в сети
Аватара пользователя

Зарегистрирован: Вт мар 20, 2007 23:39
Сообщения: 1261
Благодарил (а): 3 раз.
Поблагодарили: 19 раз.
garbler писал(а):
может, лучше, для таких случаев раздел-(файло/исходнико)помойку на форуме создать?

http://everfall.com/paste/

_________________
Cтоимость сопровождения программного обеспечения пропорциональна квадрату творческих способностей программиста.
Роберт Д. Блисc


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт янв 24, 2008 23:51 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
garbler писал(а):
mOleg писал(а):дайте пожалуйста ссылку на код
garbler писал(а):
mOleg писал(а):(если надо, могу разместить у себя).
было-бы неплохо.... если можно.

постоянного сайта у меня нет (безалаберность)

перенес примеры на Прологе и Перле, в сообщении оставил ссылки на них.

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 16


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB