Generowanie ciągu

Odpowiedz Nowy wątek
2011-08-16 14:41
0

Chcę zbudować iterator do generowania dwóch (bardzo zbliżonych) typów nieskończonych ciągów. Nazwijmy je "dwójkowy" i "trójkowy".

Dwójkowy ma postać:
aabaabcaabaabcdaabaabcaabaabcde....

Trójkowy ma postać:
aaabaaabaaabcaaabaaabaaabcaaabaaabaaabcd...

Dwójkowy można zbudować tak:

  1. Startujemy od ciągu złożonego z jednej litery
  2. W każdej kolejnej iteracji, łączymy ciąg ze swoją kopią, a na koniec dodajemy najmniejszą, nie użytą jeszcze literę.

Kolejne kroki konstrukcji wyglądają więc tak:

  1. a
  2. aab
  3. aabaabc
  4. aabaabcaabaabcd
    itd

Trójkowy można zbudować analogicznie, tylko w punkcie drugim, zamiast łączenia z jedną dodatkową kopią, łączymy z dwiema dodatkowymi kopiami.

Zamiast sklejania ciągów chcę mieć jednak iterator do generowania ciągów. Po wygenerowaniu n-tego znaku iterator powinien zawierać w sobie stan o rozmiarze O(lg n) (względnie O(lg2 n) jeżeli zakładamy zmienną długość typów danych, np BigInteger, ale załóżmy, dla prostoty, że nie wygenerujemy nigdy więcej jak np 260 znaków). Wygenerowanie jednego znaku (w dowolnym stanie iteratora) powinno mieć złożoność zamortyzowaną O(1).

Ma ktoś pomysł? :D

PS:
A może takie ciągi mają już swoją nazwę i ktoś ma już sposób na ich generowanie?


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 2x, ostatnio: Wibowit, 2011-08-16 15:41

Pozostało 580 znaków

2011-08-16 19:52
0

Już sobie poradziłem z tym :) Znalazłem podobny ciąg na oeis.org, poczytałem trochę o nim i wpadłem na pomysł jak to zrobić :) Da się to zrobić nawet zakładając wielkość stanu iteratora rzędu O(1) (czy też O(lg n) jeżeli zakładamy zmienną długość typów danych, ale komu trzeba więcej niż 2^64 elementów? :P ). Pomocne linki: http://oeis.org/A082850 , http://oeis.org/A001511 . Te linki obrazują ciągi "dwójkowe", ale ich uogólnienie (na "trójkowe", "czwórkowe", itd) okazało się dość proste.

Ciągi te są mi przydatne do wyznaczenia optymalnego (ze względu na wykorzystanie pamięci podręcznej procesora) porządku scalania w sortowaniu przez scalanie. Oczywiście nie sortuję liczb (tutaj lepszy jest poczciwy QuickSort), ale łańcuchy znaków (tutaj minimalizacja ilości dostępów do RAMu jest bardzo ważna).


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 1x, ostatnio: Wibowit, 2011-08-16 20:03

Pozostało 580 znaków

2011-08-16 20:24
2

Nie chce mi się opisywać rozwiązania, a skanera nie mam, trzymaj:

#include <iostream>
#include <vector>
using namespace std;
struct state{
    long currit;
    vector<bool> its;
    state():currit(0),its(16){}
    char next(){
        char ret='a'+currit;
        if (its[currit]) {
            its[currit]=false;
            currit++;
        }
        else {
            its[currit]=true;
            currit=0;
        }
        return ret;
    }
 
};
int main(){
    state s;
    for (int i=0; i<100; i++) cout<<s.next();
} 
Nie zauważyłem poprzedniego postu. - Zjarek 2011-08-16 20:25

Pozostało 580 znaków

2011-08-16 20:59
0

Dobra robota :) Zajrzałeś do oeis.org albo znalazłeś pomysł na necie, czy wszystko sam wymyśliłeś?

Ja naskrobałem już wersję uogólnioną, która dodatkowo wypisuje parametry scalania:

import java.util.Arrays;
 
class Tuple {
 
    final int x;
    final int y;
    final int z;
 
    Tuple(final int x, final int y, final int z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }
}
 
class SmartGenerator {
 
    final int base;
    final int length;
    int[] values = new int[20];
    int[] starts = new int[20];
    int[] powers = new int[20];
    int direction = 0;
    int position = 0;
    int upperLimit = 0;
    int lowerLimit = 0;
 
    SmartGenerator(final int base, final int length) {
        this.base = base;
        this.length = length;
 
        Arrays.fill(values, 0);
        Arrays.fill(starts, 0);
 
        for (int i = 0, power = 1; i < powers.length; i++) {
            powers[i] = power;
            power *= base;
        }
    }
 
    Tuple next() {
        if (position == upperLimit) {
            upperLimit = lowerLimit;
            while (++values[upperLimit] == base) {
                values[upperLimit] = 0;
                upperLimit++;
            }
            while (starts[lowerLimit] >= length) {
                lowerLimit++;
            }
            direction ^= (position ^ lowerLimit) & 1;
            position = lowerLimit;
        } else {
            direction ^= 1;
            position++;
        }
        Tuple result = new Tuple(starts[position], powers[position], direction);
        starts[position] += powers[position + 1];
        return result;
    }
}
 
class DumbGenerator {
 
    final int base;
    int[] values = new int[20];
    int[] starts = new int[20];
    int[] powers = new int[20];
    int direction = 0;
    int position = 0;
    int upperLimit = 0;
 
    DumbGenerator(final int base) {
        this.base = base;
 
        Arrays.fill(values, 0);
        Arrays.fill(starts, 0);
 
        for (int i = 0, power = 1; i < powers.length; i++) {
            powers[i] = power;
            power *= base;
        }
    }
 
    Tuple next() {
        if (position == upperLimit) {
            upperLimit = 0;
            while (++values[upperLimit] == base) {
                values[upperLimit] = 0;
                upperLimit++;
            }
            direction ^= position & 1;
            position = 0;
        } else {
            direction ^= 1;
            position++;
        }
        Tuple result = new Tuple(starts[position], powers[position], direction);
        starts[position] += powers[position + 1];
        return result;
    }
}
 
public class Main {
 
    void run() {
        final int base = 3;
        int length = 100;
        SmartGenerator smartGenerator = new SmartGenerator(base, length);
        DumbGenerator dumbGenerator = new DumbGenerator(base);
        int start;
        int end;
        do {
            Tuple tuple1;
            do {
                tuple1 = dumbGenerator.next();
                start = tuple1.x;
                end = start + tuple1.y * base;
            } while (start >= length);
            Tuple tuple2 = smartGenerator.next();
            if ((tuple1.x != tuple2.x) || (tuple1.y != tuple2.y) || (tuple1.z != tuple2.z)) {
                System.out.println("Błąd!");
            }
            System.out.printf("Start: %8d, stride: %8d, direction: %d\n",
                    tuple1.x, tuple1.y, tuple1.z);
        } while ((start > 0) || (end < length));
    }
 
    public static void main(String[] args) {
        long nanoTime = System.nanoTime();
        new Main().run();
        System.out.println("Time: " + (double) (System.nanoTime() - nanoTime) / 1e9 + "s");
    }
}

start = od którego miejsca scalać
stride = rozmiary posortowanych podtablic
direction = określa, z której tablicy mamy brać elementy, a do której zapisywać


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 1x, ostatnio: Wibowit, 2011-08-16 22:06
Na oeis nie byłem, 45 minut, długopis i dużo papieru. Jak to sobie rozpisałem w formie choinki, to wtedy na to wpadłem. - Zjarek 2011-08-16 21:02

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0