Generowanie ciągu :: 4programmers.net

Wibowit

2011-08-16T14:41:59+02:00

Rejestracja: dni
Ostatnio: dni
Lokalizacja: XML Hills

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:

Startujemy od ciągu złożonego z jednej litery
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:

a
aab
aabaabc
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(lg^{2 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 2}60 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?

Wibowit

2011-08-16T19:52:36+02:00

Rejestracja: dni
Ostatnio: dni
Lokalizacja: XML Hills

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).

Zjarek

2011-08-16T20:24:56+02:00

Rejestracja: dni
Ostatnio: dni

2

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

Kopiuj

#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();
}

Wibowit

2011-08-16T20:59:55+02:00

Rejestracja: dni
Ostatnio: dni
Lokalizacja: XML Hills

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:

Kopiuj

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ć