элегантное решение. работа со строками.

[hellfire]

элегантное решение. работа со строками.

не ищу )) вспомнил в разговоре с корефаном свой древний код на си, поразился

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

>>ABC

<<
A
B
C
AB
AC
BC
BA
CA
CB
ABC
.......
ну и так далее )


фишка в том, что он у меня был не рекурсивным, ибо на больших длинах строки память массива отжиралась нереально )

но функция оч. длинная и запутанная.

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

 

[Prividenie]

могу свой алго выложить, если найду

ложи

 

[vlad7]

Ложите, Оршанскому на затравку. Он ее в 1 сек. на Хаскелле сделает, рекурсии - его конек

 

[Supostat]

А можно уточнить?

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

>>ABC

<<
A
B
C
AB
AC
BC
BA
CA
CB
ABC
.......
ну и так далее )

дело в том, что для "АВС" подстрокой не является, например, "СА".
А если нужны все комбинации символов (что Вы описали в примере), то вот решение на шарпе:

  public class MyStringer
    {
        static string analizedString;
        static List<string> combinations = new List<string>();
        static List<int> usedIndex = new List<int>();
        static StringBuilder substring = new StringBuilder();

        public static List<string> GetCombinations(string s)
        {
            analizedString = s;                       
            GetNextChar();
            return combinations;
        }
        static void GetNextChar()
        {
            for (int i=0;i<analizedString.Length;i++)
            {
                char ch = analizedString[i];
                if (!usedIndex.Contains(i))
                {
                    substring.Append(ch);
                    usedIndex.Add(i);
                    combinations.Add(substring.ToString());
                    GetNextChar();
                    usedIndex.Remove(i);
                    substring.Remove(substring.Length - 1, 1);
                }
            }
        }
    }

И ещё:

фишка в том, что он у меня был не рекурсивным, ибо на больших длинах строки память массива отжиралась нереально )

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

 

[hellfire]

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

рекурсия ко всему прочему, хранит в памяти все копии массивов в промежуточных вычислениях.

 

[Supostat]

рекурсия ко всему прочему, хранит в памяти все копии массивов в промежуточных вычислениях.

Какие копии массивов в моём коде? StringBuilder и массив usedIndex достигают длины исходной строки каждый, и один массив для результатов строк! ЭТО ВСЁ.

 

[dr_mousefly]

Ложите, Оршанскому на затравку. Он ее в 1 сек. на Хаскелле сделает, рекурсии - его конек

Герцог щя скромно программирует на си.
Вы явно не в курсе последних дворцовых сплетен.

 

[joker]

ммм, или я чтото неправильно понял или задача является фактически классикой комбинаторики - перестановки всех сочетаний от 1 до длины строки...

 

[Supostat]

ммм, или я чтото неправильно понял или задача является фактически классикой комбинаторики - перестановки всех сочетаний от 1 до длины строки...

Почему Вы считаете, что могли неправильно понять? Да, комбинаторика.

 

[lugal]

Не люблю масштабируемую, в зависимости от объемоф данных рекурсию. Ибо как назло момент када боливаор не выдерживает двоих, тобишь стэк оверфлоу) настает в самый неподходящий момент. Приходитсо сидеть и с куркулятором высчитывать максимальную гулбину рекурсии.

 

[Supostat]

Не люблю масштабируемую, в зависимости от объемоф данных рекурсию. Ибо как назло момент када боливаор не выдерживает двоих, тобишь стэк оверфлоу) настает в самый неподходящий момент. Приходитсо сидеть и с куркулятором высчитывать максимальную гулбину рекурсии.

Кто ж такое полюбит? К счастью здесь не тот случай.

 

[generatorglukoff]

возвращает массив со всеми комбинациями всех подстрок
...

расшифруйте. почему ABBC не катит - подстроки AB и BC?

 

[vlad7]

Ну, да, здесь же вроде к-во возможных вариантов N(1!+...+(N-1)!)+N!, если я не ошибаюсь, не трудно прикинуть, шо творится с памятью, даже если в строке 10 символов при рекурсии

Герцог щя скромно программирует на си.
Вы явно не в курсе последних дворцовых сплетен.

Опускается. Скоро до ассемблера дойдет. Ув. г-н Оршански, хочется увидеть решение со строками на ассемблере (рекурсивное и итерационное для сравнения кол-ва строк в программах)

 

[AS0kol]

Ну, да, здесь же вроде к-во возможных вариантов N(1!+...+(N-1)!)+N!, если я не ошибаюсь, не трудно прикинуть, шо творится с памятью, даже если в строке 10 символов при рекурсии

 

[vlad7]

А что здесь n и что здесь k ? n - это к-во символов в строке, да? а k ?

Вы подходящую к данному случаю формулу скопипастили?

 

[AS0kol]

Картинка кликабельна.

Если хранить промежуточные варианты в памяти в массивах, то памяти нужно n! (когда k=n).

Почему же неуместна?

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

 

[vlad7]

Картинка кликабельна.

Если хранить промежуточные варианты в памяти в массивах, то памяти нужно n! (когда k=n).

Почему же неуместна?

А, Вы формулу не для общего кол-ва комбинаций привели?
Если для общего кол-ва комбинаций, то она не подходит, по-моему, к условию задачи. А памяти нужно гораздо больше, чем n!

n! - это только если комбинации всех символов (без комбинаций каждго символа с другими по отдельности)!!

 

[AS0kol]

Нда. А додумать самому слабо?

 

[vlad7]

Дык я и додумал - N(1!+...+(N-1)!)+N!

может, коряво , но вроде оно

 

[AS0kol]

Ты это имел в виду?



Самое интересное, что каждый следующий массив уже содержит в себе предыдущий. Можно формировать массив строк для случая n = k и дергать оттуда значения. Массив можно формировать по алгоритму сортировки, реализованном в BidirectionalIterator из STL (next_permutation и prev_permutation).