[R][Java] Generowanie podzbiorów 0-1

[Hodor]

Mam taki problem:
Wszystkich n- elementowych ciągów \(\displaystyle{ 0-1}\) jest jak wiemy \(\displaystyle{ 2^n}\) (pomijając \(\displaystyle{ 0000 \ldots 0}\) mamy ich \(\displaystyle{ 2^n-1}\))

np \(\displaystyle{ 3}\) elementowych jest \(\displaystyle{ 7}\)

\(\displaystyle{ 100\\
010\\
001\\
110\\
101\\
011\\
111}\)

Problem w tym, że dla \(\displaystyle{ n=30}\) mamy \(\displaystyle{ 1 073 741 823}\) ciągów a chciałbym mieć to zapisane w macierzy czyli 30 kolumn i dużo dużo wierszy (\(\displaystyle{ 1073741823}\)). Niestety program mi się wysypuje bo za dużo pamięci potrzebuje i komp się buntuje.

Generalnie napisałem funkcję która mi to generuje i działa dla mniejszych \(\displaystyle{ n}\)

Znalazłem rozwiązanie ale nie wiem jak zastosować:
Można podzielić rozwiązanie na kilka części np:
żeby najpierw program wypisał m pierwszych wyników a później pozostałe
np
\(\displaystyle{ 100\\
010\\
001\\
110}\)

a później
\(\displaystyle{ 101\\
011\\
111}\)

Nie wiem jednak jak napisać by program "wiedział" od czego ma zacząć wypisywać drugą macierz ani też na czym zakończył pierwszą. W ogólniejszym przypadku jak podzielić wypisywanie na \(\displaystyle{ M}\) macierzy.

Reasumując chciałbym zapytać czy jest jakiś szybki sposób na to by program wypisał powiedzmy \(\displaystyle{ 16}\) tablic (\(\displaystyle{ 30}\) kolumn po \(\displaystyle{ 67108864}\) wierszy [no w rzeczywistości \(\displaystyle{ 15}\) z \(\displaystyle{ 67108864}\) wierszami a jedną z \(\displaystyle{ 67108863}\) wierszami])
by w rezultacie dostać wszystkie kombinacje \(\displaystyle{ 0-1}\) ciągów \(\displaystyle{ 30}\) element-owych (bez samych zer).

[Afish]

Bez kodu źródłowego nie da się powiedzieć (szklane kule wyszły z mody). Najczystszym rozwiązaniem jest użycie generatora i konsumowanie wyniku na bieżąco. Mniej magicznym rozwiązaniem jest przekazywanie funkcji parametru wskazującego na pierwszy element porcji danych, w tym przypadku jest to trywialne, bo ciągi zero-jedynkowe to po prostu liczby binarne.

[Hodor]

Do generowania napisałem coś takiego (piszę w R):

Kod: Zaznacz cały

tablica=as.matrix(expand.grid(rep(list(0:1), N)))[-1]

ale dla \(\displaystyle{ N=30}\) mamy \(\displaystyle{ 1073741823}\) wiersze i brak mi pamięci by program działał.

więc wymyśliłem coś takiego:

Kod: Zaznacz cały

for(k in 1:8)
{
P=1+(i-1)*(2^N)/8
K=i*((2^N)/8)           #K=2^(N-3)

tablica=as.matrix(expand.grid(rep(list(0:1), 30)))[P:K,]
}

\(\displaystyle{ P}\) i \(\displaystyle{ K}\) to początek i koniec wypisywania w i tym kroku.

ake pojawił się problem - program nadpisuje tą samą "tablicę" i w rezultacie dostaję ostatnią ósmą.

W jaki sposób mam napisać by program tworzył w pętli nową macierz o innej nazwie i do niej zapisywał poszczególne "tablice".

Pozdrawiam

[mihile]

Nie rozumiem dlaczego generujesz te ciągi, ja bym po prostu wypisał wszystkie liczby od \(\displaystyle{ 1}\) do \(\displaystyle{ 2^{N} - 1}\) w zapisie binarnym (ew. zapisywał je do pliku).

Zapisanie tych wszystkich macierzy w pamięci kosztowałoby Cię (zakładając, że \(\displaystyle{ N = 30}\) i liczba całkowita jest zapisana na 4 bajtach oraz, że wykorzystamy tylko tablice liczb całkowitych nawet dla małych liczb w ramach uproszczenia) około \(\displaystyle{ 4}\) gigabajtów.

[Hodor]

Nie rozumiem dlaczego generujesz te ciągi, ja bym po prostu wypisał wszystkie liczby

bo

"i brak mi pamięci by program działał".

Poza tym tu nie chodzi o sens - tylko jest mi to potrzebne podzielone i generowane przez program (to kawałek większej całości) stąd moje pytanie.

Więc ponawiam pytanie

W jaki sposób mam napisać by program w R, tworzył w pętli nową macierz o innej nazwie i do niej zapisywał poszczególne "tablice".