Policz tablice okresów

11

periodZ ciągiem jest najkrótsza niezerowe przesunięcie tak, że ciąg pasuje do siebie, ignorując wszelkie części nawisu. Na przykład abcabcabma kropkę 3. Zgodnie z konwencją mówimy, że jeśli nie ma takiego przesunięcia, łańcuch ma okres równy jego długości. Więc okres abcdejest 5i okres ajest 1.

Mówiąc bardziej formalnie, okres ciągu znaków Sjest minimalny, i > 0więc S[1,n-i] == S[i+1,n](indeksowanie od 1).

Dla danego ciągu S potęgi dwóch długości obliczymy okres wszystkich jego prefiksów potęgi dwóch długości. Rozważmy na przykład S = abcabcab. Okresy, które obliczymy, to:

'a', 1
'ab', 2
'abca', 3
'abcabcab', 3

To znaczy po prostu wyprowadzimy tablicę okresów [1, 2, 3, 3].

Dla danej dodatniej mocy dwóch nrozważ wszystkie możliwe ciągi binarne S. Przypomnij sobie, że ciąg binarny jest po prostu ciągiem 1s i 0s, więc istnieją dokładnie 2^ntakie ciągi (czyli 2do potęgi n). Dla każdego z nich możemy obliczyć tę tablicę okresów.

Wyzwanie polega na napisaniu kodu, który pobiera n(potęga dwóch) danych wejściowych i oblicza, ile jest różnych takich tablic.

Odpowiedzi na n = 1, 2, 4, 8, 16, 32, 64, 128to:

1, 2, 6, 32, 320, 6025, 216854, 15128807

Pełny zestaw różnych tablic okresowych dla n = 4:

1, 1, 1
1, 1, 3
1, 1, 4
1, 2, 2
1, 2, 3
1, 2, 4

Wynik

Uruchomię Twój kod na moim komputerze z systemem Ubuntu przez 10 minut. Twój wynik jest największy, ndla którego Twój kod kończy się w tym czasie. W przypadku remisu nwygrywa odpowiedź, która zakończy wspólne największe najszybsze. W przypadku remisu w czasie 1 sekundy wygrywa pierwsza opublikowana odpowiedź.

Języki i biblioteki

Możesz użyć dowolnego dostępnego języka i bibliotek, które ci się podobają. Proszę podać pełne wyjaśnienie, w jaki sposób uruchomić / skompilować kod w systemie Linux, jeśli to w ogóle możliwe

Twój kod powinien w rzeczywistości obliczać odpowiedzi, a nie na przykład generować wstępnie obliczonych wartości.

Wiodące wpisy

  • 2 minuty i 21 sekund dla n = 128 w języku C # autorstwa Petera Taylora
  • 9 sekund dla n = 32 w Rust przez isaacg

źródło
To spowodowało ból głowy.
Henry
1
Wyzwanie jest interesujące, ale wciąż nie widzę obiektywnego kryterium, którego używasz do rozróżnienia odpowiedzi „wstępnie obliczonych” i „faktycznie obliczonych” . Jeśli na przykład nie rozumiesz, jak działa mój kod, ale daje poprawne odpowiedzi dla ogromnej n, czy zaakceptowałbyś go? Nie jest dobrze określone, gdzie jest granica między kodowaniem na twardo a faktycznym przetwarzaniem.
A123903 ?
H.PWiz
1
@ThePirateBay codegolf.meta.stackexchange.com/a/1063/9206 . To standardowa zasada.
2
@Cowsquack Wszystkie oprócz pierwszych trzech liter ciągu abcab. Wszystkie oprócz ostatnich 3 liter są abcab. Te pasują i usunięcie mniejszej liczby liter nie pasuje.
isaacg

Odpowiedzi:

9

C #, n = 128 w około 2:40

using System;
using System.Collections.Generic;
using System.Linq;

namespace Sandbox
{
    class PPCG137436
    {
        public static void Main(string[] args)
        {
            if (args.Length == 0) args = new string[] { "1", "2", "4", "8", "16", "32", "64", "128" };

            foreach (string arg in args)
            {
                Console.WriteLine(Count(new int[(int)(0.5 + Math.Log(int.Parse(arg)) / Math.Log(2))], 0));
            }
        }

        static int Count(int[] periods, int idx)
        {
            if (idx == periods.Length)
            {
                //Console.WriteLine(string.Join(", ", periods));
                return 1;
            }

            int count = 0;
            int p = idx == 0 ? 1 : periods[idx - 1];
            for (int q = p; q <= 1 << (idx + 1); q++)
            {
                periods[idx] = q;
                if (q == p || q > 1 << idx || p + q - Gcd(p, q) > 1 << idx && UnificationPasses(periods, idx, q)) count += Count(periods, idx + 1);
            }

            return count;
        }

        private static int Gcd(int a, int b)
        {
            while (a > 0) { int tmp = a; a = b % a; b = tmp; }
            return b;
        }

        private static bool UnificationPasses(int[] periods, int idx, int q)
        {
            UnionSet union = new UnionSet(1 << idx);
            for (int i = 0; i <= idx; i++)
            {
                for (int j = 0; j + periods[i] < Math.Min(2 << i, 1 << idx); j++) union.Unify(j, j + periods[i]);
            }

            IDictionary<int, long> rev = new Dictionary<int, long>();
            for (int k = 0; k < 1 << idx; k++) rev[union.Find(k)] = 0L;
            for (int k = 0; k < 1 << idx; k++) rev[union.Find(k)] |= 1L << k;

            long zeroes = rev[union.Find(0)]; // wlog the value at position 0 is 0

            ISet<int> onesIndex = new HashSet<int>();

            // This can be seen as the special case of the next loop where j == -1.
            for (int i = 0; i < idx; i++)
            {
                if (periods[i] == 2 << i) onesIndex.Add((2 << i) - 1);
            }
            for (int j = 0; j < idx - 1 && periods[j] == 2 << j; j++)
            {
                for (int i = j + 1; i < idx; i++)
                {
                    if (periods[i] == 2 << i)
                    {
                        for (int k = (1 << j) + 1; k <= 2 << j; k++) onesIndex.Add((2 << i) - k);
                    }
                }
            }

            for (int i = 1; i < idx; i++)
            {
                if (periods[i] == 1) continue;

                int d = (2 << i) - periods[i];
                long dmask = (1L << d) - 1;
                if (((zeroes >> 1) & (zeroes >> periods[i]) & dmask) == dmask) onesIndex.Add(periods[i] - 1);
            }

            long ones = 0L;
            foreach (var key in onesIndex) ones |= rev[union.Find(key)];

            if ((zeroes & ones) != 0) return false; // Definite contradiction!

            rev.Remove(union.Find(0));
            foreach (var key in onesIndex) rev.Remove(key);

            long[] masks = System.Linq.Enumerable.ToArray(rev.Values);

            int numFilteredMasks = 0;
            long set = 0;
            long M = 0;
            for (int i = 1; i <= idx; i++)
            {
                if (periods[i - 1] == 1) continue;

                // Sort the relevant masks to the start
                if (i == idx) numFilteredMasks = masks.Length; // Minor optimisation: skip the filter because we know we need all the masks
                long filter = (1L << (1 << i)) - 1;
                for (int j = numFilteredMasks; j < masks.Length; j++)
                {
                    if ((masks[j] & filter) != 0)
                    {
                        var tmp = masks[j];
                        masks[j] = masks[numFilteredMasks];
                        masks[numFilteredMasks++] = tmp;
                    }
                }

                // Search for a successful assignment, using the information from the previous search to skip a few initial values in this one.
                set |= (1L << numFilteredMasks) - 1 - M;
                M = (1L << numFilteredMasks) - 1;
                while (true)
                {
                    if (TestAssignment(periods, i, ones, masks, set)) break;
                    if (set == 0) return false; // No suitable assignment found

                    // Gosper's hack with variant to reduce the number of bits on overflow
                    long c = set & -set;
                    long r = set + c;
                    set = (((r ^ set) >> 2) / c) | (r & M);
                }
            }

            return true;
        }

        private static bool TestAssignment(int[] periods, int idx, long ones, long[] masks, long assignment)
        {
            for (int j = 0; j < masks.Length; j++, assignment >>= 1) ones |= masks[j] & -(assignment & 1);
            for (int i = idx - 1; i > 0; i--) // i == 0 is already handled in the unification process.
            {
                if (Period(ones, 2 << i, periods[i - 1]) < periods[i]) return false;
            }

            return true;
        }

        private static int Period(long arr, int n, int min)
        {
            for (int p = min; p <= n; p++)
            {
                // If the bottom n bits have period p then the bottom (n-p) bits equal the bottom (n-p) bits of the integer shifted right p
                long mask = (1L << (n - p)) - 1L;
                if ((arr & mask) == ((arr >> p) & mask)) return p;
            }

            throw new Exception("Unreachable");
        }

        class UnionSet
        {
            private int[] _Lookup;

            public UnionSet(int size)
            {
                _Lookup = new int[size];
                for (int k = 0; k < size; k++) _Lookup[k] = k;
            }

            public int Find(int key)
            {
                var l = _Lookup[key];
                if (l != key) _Lookup[key] = l = Find(l);
                return l;
            }

            public void Unify(int key1, int key2)
            {
                int root1 = Find(key1);
                int root2 = Find(key2);

                if (root1 < root2) _Lookup[root2] = root1;
                else _Lookup[root1] = root2;
            }
        }
    }
}

Rozszerzenie do n = 256 wymagałoby przełączenia BigIntegerna maski, co prawdopodobnie zabija wydajność zbyt mocno, aby n = 128 mógł przejść bez nowych pomysłów, nie mówiąc już o n = 256.

Pod Linuksem kompiluj mono-csci wykonuj za pomocą mono.

Podstawowe wyjaśnienie

Nie zamierzam dokonywać szczegółowej analizy, tylko przegląd pojęć.

Zasadniczo chętnie powtarzam w kolejności 2 50 elementów w programie kombinatorycznym typu brute-force. Aby dostać się do n = 128, konieczne jest zatem zastosowanie podejścia, które nie analizuje każdego ciągu bitów. Więc zamiast pracować naprzód od ciągów bitów do sekwencji kropek, pracuję wstecz: czy biorąc pod uwagę sekwencję kropek, czy istnieje ciąg bitów, który to realizuje? Dla n = 2 x jest łatwa górna granica 2 x (x + 1) / 2 sekwencji okresowych (w porównaniu do 2 2 x ciągów bitów).

Niektóre argumenty używają lematu okresowości łańcucha :

Niech pi qdwa okresy ciąg długości n. Jeśli p + q ≤ n + gcd(p, q)wtedy gcd(p, q)jest także kropka ciągu.

Wlog Zakładam, że wszystkie rozważane ciągi bitów zaczynają się od 0.

Biorąc pod uwagę sekwencję okresów, w której występuje okres prefiksu o długości 2 i ( zawsze), istnieją pewne łatwe obserwacje dotyczące możliwych wartości :[p1 p2 ... pk]pip0 = 1pk+1

  • pk+1 ≥ pkponieważ okres ciągu znaków Sjest również okresem dowolnego prefiksu S.

  • pk+1 = pk jest zawsze możliwym rozszerzeniem: wystarczy powtórzyć ten sam prymitywny ciąg dla dwóch razy większej liczby znaków.

  • 2k < pk+1 ≤ 2k+1jest zawsze możliwym rozszerzeniem. Wystarczy to wykazać, ponieważ aperiodyczny ciąg długości można przedłużyć do aperiodycznego ciągu długości , dodając dowolną literę, która nie jest jego pierwszą literą.pk+1 = 2k+1LL+1

    Weź łańcuch Sxo długości 2 k, którego okres jest, i rozważ łańcuch o długości 2 k + 1 . Wyraźnie ma na okres 2 k +1. Załóżmy, że jego okres jest krótszy.pkSxySSxySq

    Zatem przez okresowość lemat jest także okresem , a ponieważ największy dzielnik jest mniejszy lub równy swoim argumentom i jest najmniejszym okresem, musimy mieć odpowiedni współczynnik 2 k +1. Ponieważ jego iloraz nie może wynosić 2, mamy .2k+1 + q ≤ 2k+1+1 ≤ 2k+1 + gcd(2k+1, q)gcd(2k+1, q)SxySqqq ≤ (2k+1)/3

    Teraz, ponieważ jest to okres, który musi być okresem . Ale okres jest . Mamy dwa przypadki:q ≤ 2kSxySSxSxpk

    1. gcd(pk, q) = pklub równo dzieli się na .pkq
    2. pk + q > 2k + gcd(pk, q) aby lemat okresowości nie wymuszał krótszego okresu.

    Rozważ najpierw drugi przypadek. , co jest sprzeczne z definicją okresu . Dlatego jesteśmy zmuszeni dojść do wniosku, że jest to czynnik .pk > 2k + gcd(pk, q) - q ≥ 2k+1 - q ≥ 2k+1 - (2k+1)/3 ≥ 2qpkSxpkq

    Ale ponieważ qjest to okres Sxi jest to okres , prefiks długości jest tylko kopią prefiksu długości , więc widzimy, że jest to również okres .pkSxqq/pkpkpkSxyS

    Dlatego okres SxySwynosi albo 2 k +1. Ale mamy dwie opcje ! Co najwyżej jeden wybór da okres , więc co najmniej jeden da okres 2 k +1. CO BYŁO DO OKAZANIA.pkyypk

  • Lemat okresowości pozwala nam odrzucić niektóre z pozostałych możliwych rozszerzeń.

  • Każde rozszerzenie, które nie przeszło testu szybkiego akceptowania lub szybkiego odrzucania, musi zostać przetestowane konstruktywnie.

Konstrukcja łańcucha bitów w sekwencji okresu jest zasadniczo problemem satysfakcji, ale ma wiele struktur. Istnieją proste ograniczenia równości implikowane przez każdy okres prefiksu, więc używam struktury danych zbioru unii do łączenia bitów w niezależne klastry. To wystarczyło, aby pokonać n = 64, ale dla n = 128 konieczne było pójście dalej. Używam dwóch użytecznych argumentów:2k - pk

  1. Jeśli prefiksem długości Mjest i prefiks długości ma kropkę, to prefiks długości musi kończyć się na . Jest to najsilniejsze właśnie w przypadkach, które w innym przypadku miałyby najbardziej niezależne klastry, co jest wygodne.01M-1L > MLL1M
  2. Jeśli prefiks długości Mjest, a prefiks długości ma kropkę z i kończy się w, to tak naprawdę musi on kończyć się na . Jest to najsilniejsze w przeciwnej skrajności, gdy sekwencja okresu zaczyna się od wielu.0ML > ML - dd < M0d10d

Jeśli nie otrzymamy natychmiastowej sprzeczności, zmuszając klaster z pierwszym bitem (zakładanym jako zero) do jednego, wówczas brutalnie działamy (z pewnymi mikrooptymalizacjami) nad możliwymi wartościami dla niewymuszonych klastrów. Zauważ, że kolejność jest w malejącej liczby tych, bo jeśli ity bit jest jeden, to okres ten nie może być ii chcemy uniknąć okresów, które są krótsze niż te, które są już egzekwowane przez klastry. Zejście w dół zwiększa szanse na wcześniejsze znalezienie ważnego zadania.

Peter Taylor
źródło
To naprawdę świetne osiągnięcie! Jestem pod wrażeniem.
@Lembik, uprościłem i zoptymalizowałem kod oraz skróciłem czas działania dla n = 128 o około jedną trzecią.
Peter Taylor,
1
Chciałbym wiedzieć, jaki algorytm zaprojektowałeś dla tego. Twój kod ma wyjątkowo małą logikę i musi robić coś bardzo sprytnego.
7

Rust, 32, 10s 11s 29s na moim laptopie

Wywołaj to z bitowym rozmiarem jako argumentem wiersza poleceń.

Sprytne techniki: reprezentuj ciągi bitów bezpośrednio jako liczby, użyj bittwiddling, aby sprawdzić cykle. Przeszukuj tylko pierwszą połowę ciągów bitów, zaczynających się od 0, ponieważ tablica okresów ciągu bitów i jego odwrotności (0 zamienionych na 1s) są identyczne. Jeśli pojawiła się już każda możliwość uzyskania ostatecznej pozycji, nie szukam jej.

Bardziej sprytne rzeczy:

Aby deduplikować każdy blok (ciągi, w których pierwsza połowa bitów jest taka sama), używam bitvectora, który jest znacznie szybszy niż hashset, ponieważ końcowe długości cyklu nie wymagają haszowania.

Pomijam też pierwsze kroki sprawdzania cyklu, ponieważ wiem, że ostatni cykl nie może być krótszy niż cykl od drugiego do ostatniego.

Po wielu profilach mogę teraz stwierdzić, że prawie cały czas jest produktywnie wykorzystywany, więc myślę, że w tym przypadku konieczne będą ulepszenia algorytmów. Zmieniłem również na 32-bitowe liczby całkowite, aby zaoszczędzić trochę czasu.

//extern crate cpuprofiler;
//use cpuprofiler::PROFILER;

extern crate bit_vec;
use bit_vec::BitVec;

use std::collections::HashSet;

fn cycle_len(num: u32, mask: u32, skip_steps: usize) -> usize {
    let mut left = num >> skip_steps;
    let mut mask = mask >> skip_steps;
    let mut steps = skip_steps;
    loop {
        left >>= 1;
        if left == (num & mask) {
            return steps;
        }
        mask >>= 1;
        steps += 1;
    }
}

fn all_cycles(size_log: usize) -> HashSet<Vec<usize>> {
    let mut set = HashSet::new();
    if size_log == 0 {
        set.insert(vec![]);
        return set;
    } else if size_log == 1 {
        set.insert(vec![0]);
        set.insert(vec![1]);
        return set;
    }
    let size: usize = 1 << size_log;
    let half_size: usize = 1 << size_log - 1;
    let shift_and_mask: Vec<(usize, u32)> = (1..size_log)
        .map(|subsize_log| {
            let subsize = 1 << subsize_log;
            (size - subsize, (1 << (subsize - 1)) - 1)
        })
        .collect();
    let size_mask = (1 << (size - 1)) - 1;
    for block in 0..(1 << (half_size - 1)) as u32 {
        let start: u32 = block << half_size;
        if block % 1024 == 0 {
            eprintln!(
                "{} ({:.2}%): {}",
                start,
                start as f64 / (1u64 << size - 1) as f64 * 100f64,
                set.len()
            );
        }
        let leader = {
            let mut cycles = Vec::new();
            for &(shift, mask) in &shift_and_mask {
                let subnum = start >> shift;
                cycles.push(cycle_len(subnum, mask, 0));
            }
            cycles
        };
        let &end = leader.last().unwrap();
        if (end..size).all(|count| {
            let mut new = leader.clone();
            new.push(count);
            set.contains(&new)
        })
        {
            continue;
        }
        let mut subset = BitVec::from_elem(size, false);
        for num in start..start + (1 << half_size) {
            subset.set(cycle_len(num, size_mask, end), true);
        }
        for (unique_cycle_len, _) in subset.into_iter().enumerate().filter(|x| x.1) {
            let mut new_l = leader.clone();
            new_l.push(unique_cycle_len);
            set.insert(new_l);
        }
    }
    set
}

fn main() {
    let size: f32 = std::env::args().nth(1).unwrap().parse().unwrap();
    let size_log = size.log2() as usize;
    //PROFILER.lock().unwrap().start("./my-prof.profile").unwrap();
    let cycles = all_cycles(size_log);
    //PROFILER.lock().unwrap().stop().unwrap();
    println!(
        "Number of distinct arrays of periods of bitstrings of length {} is {}",
        1 << size_log,
        cycles.len()
    );
}

Umieść bit-vec = "0.4.4"swój Cargo.toml

Jeśli chcesz to uruchomić, sklonuj to: github.com/isaacg1/cycle, a następnie Cargo build --releaseskompiluj, a następnie Cargo run --release 32uruchom.

isaacg
źródło
Wygląda na to, że eprintln potrzebuje wersji rdzy po wersji 0.16.0. Działa, jeśli zmienię go na println.
Ta odpowiedź jest bardzo imponująca. timedaje mi 27 sekund użytkownika na moim laptopie.
@Lembik, dlaczego jesteś w tak starej wersji rdzy? Rust 1.0 wyszedł wiele lat temu.
isaacg,
Typo :) Miałem na myśli 1.16.0. blog.rust-lang.org/2017/03/16/Rust-1.16.html
Czy dla początkujących rdzy nie miałbyś nic przeciwko, aby dokładnie napisać, jak skompilować kod za pomocą cargo?
4

Rdza , 16

use std::collections::HashSet;
use std::io;

fn main() {
	print!("Enter a pow of two:");
	let mut input_text = String::new();
    io::stdin()
        .read_line(&mut input_text)
        .expect("failed to read from stdin");

    let n_as_string = input_text.trim();
	match n_as_string.parse::<usize>() {
		Ok(n) => {
			let log2 = (n as f64).log(2_f64) as usize;
			if n != 1 << log2 {
				panic!("{} is not a power of two", n);
			}
			let count = compute_count_array(log2, n);
			println!("n = {} -> count = {}", n, count);
		}
		Err(_) => { panic!("{} is not a number", n_as_string); }
	}
}

fn compute_count_array(log2:usize, n: usize) -> usize {
	let mut z = HashSet::new();

	let mut s:Vec<bool> = vec!(false; n);
	loop {
		let mut y:Vec<usize> = vec!();
		for j in 0..log2+1 {
			let p = find_period(&s[0..1<<j]);
			y.push(p);
		}		
		z.insert(y);
		if !next(&mut s) {
			break;
		}
	}
	z.len()
}

#[inline]
fn find_period(s: &[bool]) -> usize {
	let n=s.len();
	let mut j=1;
	while j<n {
		if s[0..n-j] == s[j..n] {
			return j;
		}
		j+=1;
    }
	n
}	

#[inline]
fn next(s:&mut Vec<bool>) -> bool {
	if s[0] {
		s[0] = false;
		for i in 1..s.len() {
			if s[i] {
				s[i] = false;
			} else {
				s[i] = true;
				return true;
			}
		}
		return false
	} else {
		s[0] = true;
	}
	true
}

Wypróbuj online!

Kompilacja: rustc -O <name>.rs

Ciąg jest implementowany jako wektor Bool.

  • nextFunkcja iterację kombinacji;

  • find_periodBierze kawałek Bool i zwraca okresu;

  • compute_count_arrayNie praca dla każdego „mocą dwóch” podciąg każdej kombinacji Bools.

Teoretycznie nie oczekuje się przepełnienia, dopóki nie 2^nprzekroczy maksymalnej wartości u64, tj n > 64. Limit ten można przekroczyć kosztownym testem na s = [prawda, prawda, ... prawda].

Zła wiadomość: zwraca 317 dla n = 16, ale nie wiem dlaczego. Nie wiem też, czy to zajmie dziesięć minut dla n = 32, ponieważ Vec<bool>nie jest zoptymalizowane dla tego rodzaju obliczeń.

EDYTOWAĆ

  1. Udało mi się usunąć limit 64 dla n. Teraz nie nzawiedzie się, dopóki nie będzie większa niż maksymalna liczba całkowita usize.

  2. Dowiedziałem się, dlaczego poprzedni kod zwrócił 317 n=32. Liczyłem zestawy okresów, a nie tablice okresów. Były trzy tablice z tymi samymi elementami:

    [1, 2, 3, 3, 8] -> {1, 2, 3, 8}
    [1, 2, 3, 8, 8] -> {1, 2, 3, 8}
    [1, 1, 3, 3, 7] -> {1, 3, 7}
    [1, 1, 3, 7, 7] -> {1, 3, 7}
    [1, 1, 3, 3, 8] -> {1, 3, 8}
    [1, 1, 3, 8, 8] -> {1, 3, 8}
    

Teraz działa. Nadal jest wolny, ale działa.

Jferard
źródło
Oto wszystkie 320 dla n = 16 bpaste.net/show/3664e25ebc01 .
1
@Lembik Znalazłem wyjaśnienie dla 317 dzięki twojej liście.
Jferard,
2

C - 16

Nie działa przy wartościach większych niż 16 cuz przepełnienia.

Nie mam pojęcia, jak szybko to działa, bo jestem na Chromebooku, który działa na repl.it.

Po prostu implementuje pytanie w trakcie czytania, przechodzi przez wszystkie ciągi bitów, oblicza tablice kropek i sprawdza, czy zostały już policzone.

#include "stdio.h"
#include <stdbool.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

int per(int s[], int l) {
  int period = 0;
  while (1) {
    period++;

    bool check = 1;
    int i;
    for (i=0; i<l-period; i++) {
      if (s[i]!=s[i+period]) {
        check = 0;
        break;
      }
    }
    if (check) {
      return period;
    }
  }
}

bool perar(int* s, int l, int* b, int i) {
  int n = 1;
  int j=0;
  while (n<=l) {
    b[i*l+j] = per(s, n);
    n=n<<1;
    j++;
  }

  for (j=0;j<i;j++) {
    int k;
    bool check = 1;
    for(k=0; k<l; k++) {
      if (b[j*l+k] != b[i*l+k]) {
        check = 0;
        break;
      }
    }
    if (check) {
      return 0;
    }
  }
  return 1;
}

int main(int argc, char* argv[]) {
  int n;
  scanf("%d", &n);
  puts("Running...");
  int i;
  int c = 0;
  int* a = malloc(n*sizeof(int));
  int m=pow(2, n);
  int* b = malloc(m*n*sizeof(int));
  for (i=0; i<m; i++) {
    int j;
    for (j=0; j<n; j++) {
      a[j] = (i>>j)&1;
    }
    c+=perar(a, n, b, i);
  }
  printf("Answer: %d\n", c);
  return 0;
}

Po prostu skompiluj go za pomocą gcc itp.

Maltysen
źródło
FYI - To był dla erroring 16wtedy, gdy kod został zmieniony tak, że dwa mallocs były malloc(...int*))i ...**odpowiednio 16drukowane Answer: 320zgodnie z oczekiwaniami, jednak 32drukowana Answer: 0(i dość szybko).
Jonathan Allan
@JonathanAllan naprawił to, właśnie zrobił b a int *.
Maltysen
@JonathanAllan the 32 thing is cuz 2 ** 32 overflows the int. Również zabraknie mi pamięci.
Maltysen
@ThePirateBay I i m m longs, a to tylko segfault, gdy próbuję 32. repl.it/JwJl/2 Zgaduję, że zabrakło pamięci.
Maltysen
@Maltysen. Wygląda na to, że występuje awaria, ponieważ popsułeś coś w alokacji / dezalokacji zamiast braku dostępnej pamięci. Dostałem segfault, n = 8ale po wydrukowaniu wyniku, co oznacza, że ​​stos jest uszkodzony. Prawdopodobnie piszesz gdzieś poza przydzielonymi blokami pamięci.
2

Haskell

import qualified Data.Set as S
import Data.Bits

period :: Int -> Int -> Int
period num bits = go (bits-2) (div prefix 2) (clearBit prefix $ bits-1)
  where
  prefix = (2^bits-1) .&. num
  go p x y
    | x == y    = p
    | otherwise = go (p-1) (div x 2) (clearBit y p)

allPeriods :: Int ->  [[Int]]
allPeriods n = map periods [0..div(2^n)2-1]
  where
  periods num = map (period num) powers
  powers = takeWhile (<=n) $ iterate (*2) 2

main = readLn >>= print . S.size . S.fromList . allPeriods

Kompiluj z ghc -O2. Wypróbuj online!

Działa w czasie krótszym niż 0,1 sekundy na moim 6-letnim laptopie dla n=16. n=32zajmuje 99 92min, więc mam 9 lub 10 zniżki. Próbowałem buforować kropki w tabeli odnośników, więc nie muszę ich ponownie obliczać w kółko, ale na moim komputerze o pojemności 4 GB szybko kończy się pamięć.

nimi
źródło
Pomimo tego, że współczynnik wynosi 10, kod wygląda bardzo dobrze.
@Lembik. Dzięki. Próbuję tylko ulepszenia: powyższy kod oblicza okresy dla podciągów o długości 1, ale to zupełnie niepotrzebne. Oprócz tego, że nie trzeba ich obliczać, oszczędza to również trochę czasu przy wyszukiwaniu unikalnych tablic okresów, ponieważ wszystkie są krótsze o jeden element.
nimi
@Lembik: pominięcie podciągów o długości 1 oszczędza około 7 minut dla n = 32. Nadal o wiele za długo.
nimi
Istnieje szybki algorytm liniowy do obliczania okresu, który może pomóc.
Czy naprawdę nie możesz zbudować tabeli przeglądowej o rozmiarze 2 ^ 16? To nie wydaje się zbyt duże.
1

Python 2 (PyPy), 16

import sys
import math
def do(n):
 masks=[]
 for i in range(n):
  masks+=[(1<<((2<<i)-1))-1]
 s=set()
 bits=1<<n
 for i in xrange(1<<bits):
  r=[0,]*n
  for j in range(len(masks)):
   mask=masks[j]
   k,c=i>>bits-(2<<j),1
   d=k>>1
   while k&mask^d:
    d>>=1
    mask>>=1
    c+=1
   r[j]=c
  s|={tuple(r)}
 return len(s)
print do(int(math.log(int(sys.argv[1]),2)))
Tylko ASCII
źródło
: | dlaczego 32 musi trwać tak długo
tylko ASCII
Wiem, że mogę pominąć połowę z nich, ale IDK jak: /
Tylko ASCII
Wydaje mi się, że twój kod wyświetla tylko „Brak”. Jak to działa? osboxes@osboxes:~/python$ python ascii_user.py 16 None
cholera przepraszam, to nie jest tak naprawdę to, co uruchamiam
tylko ASCII
@Lembik naprawiony teraz
tylko ASCII
1

[C ++], 32, 4 minuty

#include <iostream>
#include <vector>

typedef unsigned int u;
template<typename T, typename U>
u Min(T a, U b) {
    return a < b ? a : b;
}

template<typename T, typename U>
u Max(T a, U b) {
    return a > b ? a : b;
}

u Mask(int n) {
    if (n < 0) n = 0;
    return ~((u)(-1) << n);
}
u MASKS[32];

inline u Rshift(u v, int n) {
    return n < 0 ? v >> (-1*n)
    : n > 0 ? v << n
    : n;
}

int GetNextPeriodId(u pattern, int pattern_width, int prior_id) {
    int period = (prior_id % (pattern_width>>1)) + 1;
    int retval = prior_id * pattern_width;

    for (; period < pattern_width; period+=1) {
        u shift = pattern >> period;
        int remainder = pattern_width-period;
        u mask = MASKS[period];

        for (;remainder >= period && !((pattern ^ shift) & mask);
             shift >>= period, remainder -= period);

        if (remainder > period) continue;
        if (remainder == 0 || !((pattern ^ shift) & MASKS[remainder])) {
            retval += (period-1);
            break;
        }
    }
    if (period == pattern_width) {
        retval += pattern_width-1;
    }
    return retval;
}

int ParseInput(int argc, char** argv) {
    if (argc > 1) {
        switch(atoi(argv[1])) {
            case 1:
                return 1;
            case 2:
                return 2;
            case 4:
                return 4;
            case 8:
                return 8;
            case 16:
                return 16;
            case 32:
                return 32;
            default:
                return 0;
        }
    }
    return 0;
}

void PrintId(u id, int patternWidth) {
    for(;patternWidth > 0; id /= patternWidth, patternWidth >>= 1) {
        std::cout << (id % patternWidth)+1 << ",";
    }
    std::cout << std::endl;
}

int TestAndSet(std::vector<bool>& v, int i) {
    int retval = v[i] ? 0 : 1;
    v[i] = true;
    return retval;
}

std::vector<bool> uniques(1<<15);
int uniqueCount = 0;

void FillUniques(u i, int id, int target_width, int final_width) {
    int half_size = target_width / 2;
    u end = 1u<<(half_size-1);
    u mask = MASKS[half_size];
    u lowers[] = { i, (~i)&mask };
    for (u j = 0ul; j < end; j++) {
        u upper = j << half_size;
        u patterns[] = { (upper|lowers[0]), (upper|lowers[1]) };
        for (int k=0; k < sizeof(patterns)/sizeof(patterns[0]); k+=1) {
            int fid = GetNextPeriodId(patterns[k], target_width, id);
            if (target_width != final_width) {
                FillUniques(patterns[k], fid, target_width*2, final_width);
            } else {
                if (TestAndSet(uniques, fid)) {
                    uniqueCount += 1;
                }
            }
        }
    }
}

int main(int argc, char** argv) {
    for (int i = 0; i < 32; i++) {
        MASKS[i] = Mask(i);
    }
    int target_width = 32; // ParseInput(argc, argv);
    if (!target_width) {
        std::cout << "Usage: " << argv[0] << " [1|2|4|8|16|32]" << std::endl;
        return 0;
    }
    if (target_width == 1) {
        std::cout << 1 << std::endl;
        return 0;
    }
    FillUniques(0, 0, 2, target_width);
    std::cout << uniqueCount << std::endl;
    return 0;
}
Doug Coburn
źródło