Generowanie 2^n tekstów algorytm

Dla specjalistów Programowanie
#1

Witam,

mam taki problem koncepcyjny otóż chce generować teksty na podstawie ustalonego tekstu przez podwajanie konkretnych znaków

czyli (dla ułatwienia zrozumienia): tekst “abbac” (podwajam “a”) wynik:

“aabbac”, “abbaac”, “aabbaac”

i teraz pytanie jak takie coś generować dla dowolnej liczby podwajanych elementów.

Mój pomysł to w 1 etapie tworze pomocniczą tablicę z wartościami wskazujący na miejsca w których można podwoić znak

ale nie wiem jak wygenerować wszystkie 2^n (-1 który jest ustalony) ciągów.

#2 
-module(podwajanie).

-export([podwajaj/2]).


podwajaj(Slowo, Litery) ->

    podwajaj(Slowo, Litery, [[]]).


podwajaj([], _L, Prefiksy) ->

    Prefiksy;

podwajaj([H|T], L, Prefiksy) ->

    case lists:member(H, L) of

        true ->

            podwajaj(T, L, [P ++ I || I <- [[H], [H, H]], P <- Prefiksy]);

        false ->

            podwajaj(T, L, [P ++ [H] || P <- Prefiksy])

    end.

przykładowe użycie:

> podwajanie:podwajaj("abbac", "ab").

["abbac","aabbac","abbbac","aabbbac","abbbac","aabbbac",

 "abbbbac","aabbbbac","abbaac","aabbaac","abbbaac",

 "aabbbaac","abbbaac","aabbbaac","abbbbaac","aabbbbaac"]

Byłbym zapomniał… kod jest w erlangu.

#3

Chodzi ci o to że chcesz podwajać litery we wszystkich kombinacjach?

czyli z ciągu “abc” zrobić:

abcc

abbc

abbcc

aabc

aabcc

aabbc

aabbcc

dobrze rozumiem?

#4

@alex

podwajać we wszystkich kombinacjach tak ale wybrane litery nie koniecznie wszystkie

@flash4gordon

dzięki za tak dokładną odpowiedź szkoda tylko że dla mnie trochę bezużyteczną ponieważ potrzebuje to zaimplementować w języku imperatywny a nie funkcyjnym nie mniej dzięki za odpowiedź

#5

grzelix, podążając Twoim tropem:

Dla słowa “abbac” i wybranego zbioru liter {a, c}, tablica T o której wspomniałeś będzie wyglądać tak: [0, 3, 4]. Możesz stworzyć dodatkową tablicę/maskę, która wyznaczy, które elementy (spośród wcześniej wybranych) zostaną podwojone. Możesz to zrobić tak:

Zaczynasz od maski [0, 0, 0], a kolejne maski generujesz dodając 1, maskę traktując jako liczbę w systemie pozycyjnym dwójkowym:

[0, 0, 0] -> [1, 0, 0] -> [0, 1, 0] -> [1, 1, 0] -> [0, 0, 1] -> [1, 0, 1] -> [0, 1, 1] -> [1, 1, 1]

Następnie, dla każdej takiej maski przetwarzasz dane słowo, dodając dodatkową literę, jeśli jej indeks znajduje się w T oraz maska w tym miejscu maska wynosi 1. Zamiast własnych konstrukcji (choć dużo pisania tu nie ma), możesz użyć liczb całkowitych i operatorów bitowych. Jednak zwykle będą nałożone limity na 32/64 bity (co i tak powinno wystarczyć), możesz też użyć modułów bigint, które znoszą te ograniczenia.

#6

Maska nie koniecznie musi być liczbowa, może to być jakiś bitset lub nawet ciąg znaków składający się na przykład ze spacji i gwiazdek (gwiazdka tam gdzie trzeba podwoić). W takim przypadku trzeba napisać prosty algorytm dodawania jedynki:

W pętle od końca zastępujemy wszystkie kolejne jedynki na zera, jak dojdziemy do zera to zastępujemy go na jedynkę i na tym koniec.