Builder.cz - Informacni server o programovani

Odběr fotomagazínu

Fotografický magazín "iZIN IDIF" každý týden ve Vašem e-mailu.
Co nového ve světě fotografie!

 

Zadejte Vaši e-mailovou adresu:

Kamarád fotí rád?

Přihlas ho k odběru fotomagazínu!

 

Zadejte e-mailovou adresu kamaráda:

Soutěž

Sponzorem soutěže je:

IDIF

 

Kde se koná výstava fotografií Luďka Vojtěchovského?

V dnešní soutěži hrajeme o:



Jak mapovat přirozené číslo na sekvenci číslic 0-7 tak, aby se žádná číslice v sekvenci neopakovala

Seznam témat     Nová odpověď

Přihlásit se     Registrace     Zapomenuté heslo

Re: Jak mapovat přirozené číslo na sekvenci číslic 0-7 tak, aby se žádná číslice v sekvenci neopakovala

Autor: neutr ♂

12:07:27 23.05.2017

Martin Skalák napsal/a

Zdravím vás,

pro každé přirozené číslo, které se vejde do kapacity výsledku, potřebuji vytvořit unikátní čtyřmístný kód složený s číslic 0-7 tak, aby se ve výsledném kódu číslice neopakovaly. Čili např. pro jedničku by mohl být výsledek "0123", pro dvojku "0124" atd. Je žádán převod oběma směry. Tj. např. 1 = "0123", "0123" = 1. Číslo "123" v osmičkové soustavě sobě převedu na kód "0123" pochopitelně snadno. Kódy "0000" nebo "1212" jsou neplatné, neboť číslice se opakují.

Připomíná vám to některý matematický problém, o kterém já nevím?

(Líbí se mi totiž představa, že by se o převod staralo např. jen několik málo výrazů. Jinak počítám, že na to budu muset jít algoritmem, v tuto chvíli ještě nevím přesně jak, ale nějakým způsobem asi vytvořím v paměti seznam oněch unikátních kódů, index v seznamu rovná se tomu přirozenému číslu, převod opačným směrem probíhá vyhledáváním).

Třeba jste chytří a budete to někdo vědět ;) Díky za radu. M.

Martin Skalák napsal/a

pro každé přirozené číslo, které se vejde do kapacity výsledku, potřebuji vytvořit unikátní čtyřmístný kód složený .... Je žádán převod oběma směry. Tj. např. 1 = "0123", "0123" = 1. Číslo "123" v osmičkové soustavě sobě převedu na kód "0123" pochopitelně snadno. Kódy "0000" nebo "1212" jsou neplatné, neboť číslice se opakují.
Připomíná vám to některý matematický problém, o kterém já nevím? ....., v tuto chvíli ještě nevím přesně jak, ale nějakým způsobem asi vytvořím v paměti seznam oněch unikátních kódů, index v seznamu rovná se tomu přirozenému číslu, převod opačným směrem probíhá vyhledáváním).



Ano připomíná mi to určitou problematiku kterou jsem již dříve řešil. Ve skutečnosti se jedná o problematiku variací bez opakování což se dá vyjádřit například jako k!(Kombinace celku 8 a třídy 4.) Tedy Čtyřčíselných kombinací z celku 8 je 70. Každé čtyřčíslo má 4! variant = 24 - tedy celkem 1680. (také jinak vypočítáme variace stejného základu a třídy takto =8*7*6*5 = 1680.
Algoritmus není problém ale urychlení převodu (překódování/zašifrování) bez algoritmu problém být může. Existují triky jak rychle řešit pořadí ale musíme tomu dát určitý popis. Konkrétně těch 1680 čtyřčísel (variací bez opakování) reprezentuje současně 1680 pořadových hodnot "x". Tady už vidíme naznačenou array(1679,1).
To znamená že hledání podle pořadí je otázkou vyhledání indexu která je pro pořadí dán jako x-1. Opačně je to horší. Z popisu variace musíme vyčíst pořadí. Když použijeme array - není větší problém. Ale array je zřejmě nežádoucím (kompromitujícím) faktorem zejména pokud jde o nějaké klíče a podobně. (Používá se to zřejmě u čipových karet ap.) A tak je spíš žádoucí algoritmus - ten je prakticky shodný s tím který bychom použili na prohledávání skutečné array - jen se zadají pokyny scriptu (generátoru).

V jednoduchém případě použijeme rozdělování polovinou - infimum = 0,1,2,3 (=1) a supremum = 7,6,5,4 (=1680). Naší posloupnost variací vyjádříme jako UV (unique value) takto 1 = 0*1000 + 1*100 + 2*10 + 3 = 123 dekadicky. Pro supremum 1680 = 7*1000 + 6*100 + 5*10 + 4 = 7654. Někde mezi nimi je polovina (123+7654)/2 = 3888,5. Takto můžeme dělit polovinou postupně až někam kde budeme hodně blízko. Potom můžeme použít na několk kroků algoritmus - nejlépe faktoriál. Dále budeme uvažovat o řadě 0-7 jako o 1-8.
Jinou metodou je přičíst k pořadí 1234 respektive odečíst UV od suprema. Jde o přibližování. To můžeme dělat jak doleva tak doprava - předpokládáme při tom, že pořadí je uzavřeno v kruhu a proto za 8765 následuje 1 (podobně pod jedničkou - doleva je 8765). Při tom můžeme použít "vzdálenosti" UV - je jich jen několik. Například číslo 2 má UV 1243 - a rozdíl mezi jedničkou dvojkou je 9 - ale těchto hodnot je více. Přes to se můžeme přibližovat pomocí 9-ti. Například 1680/9 = cca 850 a to je asi polovina z ceku pořadí (1680).


Mimo to existuje mnohem elegantnější metoda. Ta spočívá v jiném vyhodnocení pořadí nažli "UV" ačkoliv hodnotu vypočítává stejně. Základem je pořadí kombinací - těch je pouze 70 a ještě ke všemu jsou sigmaaditivně párované. Například zadáme 1234(první) a zbytek je 5678(poslední).
No a každá kombinace má 24 variací. Potom je celkem logické :
p1 = 1234. p2 = 1243, p3 = 1324, p4 = 1342, ........p24 = 4321. Takže pořadí se skládá z pořadí kombinace + pořadí variace. Zde máme unikátní možnost měnit konvenci řazení ascendent/descendent ve dvou verzích = 4 základní možnosti ale můžeme snadno pořadí šifrovat - až faktoriál 1680 x.
Polovina končí na kombinaci 1678 a druhá začíná 2345. Pochopiteleně uděláme UV z kombinací (setřídíme tvar variace) a hledáme poloviny - nejprve ze 70, následně 35, dále 17, 9 a podobně. (Ty poloviny můžeme zadat jako statické proměnné.) Dostaneme se asi během 6 ti kroků k tomu že připočítáme číslo variace (1 až 24) - celkem asi 4 kroky. Průměrně by to nevyžadovalo více jak 11 kroků.
A co víc - pořadí je pro takto vytvořené UV "nelexikální". Jde ovšem více o účel. Jsem si docela jist že jde o čipovky 8 bitů. To co popisuji je docela snadné a myslím že až hanebně. Umím ale víc - umím kódovat pomocí 8bitů devítku (tedy rozuměj číslo 9 dekadicky) která má nedocenitelné možnosti. Představte si nadopované Sudoku. Tedy jen náznak - vyjadřovací schopnost (redundace trojic) až 10^273 ačkoliv těch 8 bitů si z toho hodně ukousne ale i tak je to astronomické množství.

Citovat příspěvek

 

Re: Jak mapovat přirozené číslo na sekvenci číslic 0-7 tak, aby se žádná číslice v sekvenci neopakovala

Autor: Martin Skalák ♂

20:02:01 12.01.2017

Huš! Neumíme, di pryč!... hmmnhmf .. aha, "repeat" je properta s významnou funkčností (vnořený cyklus), kontroluje, jsou-li v řadě stejné prvky. metoda increment() je v rekurzivním cyklu vytáří, s přenosem "carry" při přetečení. Díky.
Čili algoritmus, a pak že prý je vesmír matematicky dokonalý, hahaha

Citovat příspěvek

 

Re: Jak mapovat přirozené číslo na sekvenci číslic 0-7 tak, aby se žádná číslice v sekvenci neopakovala

Autor: TC1 ♂

14:01:57 29.11.2016

public class Septik
{
int[] data;
public Septik() { data = new int[] { 3, 2, 1, 0 }; }
public Septik(int val) :this(){for(;val>0;val--)Increment(); }

public int Value() { int val; for ( val = 0; !zero; val++)Decrement() ; return val; }
bool repeat { get { for(int i=0;i<4;i++)for(int j=i+1;j<4;j++)if(data[i]==data[j])return true; return false; } }
bool zero { get { return (data[0] == 3) && (data[1] == 2) && (data[2] == 1) && (data[3] == 0); } }
public bool Increment()
{
int carry = 1;
for(int i=0;i<4;i++)
{
data[i] += carry;
if (data[i] > 7)
{
carry = 1;
data[i]=0;
}
else carry = 0;
}
if (repeat) return Increment();
return carry == 0;
}
public bool Decrement()
{
int carry = 1;
for(int i=0;i<4;i++)
{
data[i] -= carry;
if (data[i] <0)
{
carry = 1;
data[i] =7;
}
else carry = 0;
}
if (repeat) return Decrement();
return carry == 0;
}

public override string ToString()
{
var sb = new StringBuilder();
foreach (var d in data) sb.Append(d.ToString());
return sb.ToString();
}
}
static void Main(string[] args)
{
var s = new Septik();
for(int i=0;i<50;i++)
{
if (!s.Increment()) break;
Console.WriteLine(s);
}

s=new Septik(15);
int v = s.Value();
}
}

Citovat příspěvek

 

Jak mapovat přirozené číslo na sekvenci číslic 0-7 tak, aby se žádná číslice v sekvenci neopakovala

Autor: Martin Skalák ♂

15:46:44 21.10.2016

Zdravím vás,

pro každé přirozené číslo, které se vejde do kapacity výsledku, potřebuji vytvořit unikátní čtyřmístný kód složený s číslic 0-7 tak, aby se ve výsledném kódu číslice neopakovaly. Čili např. pro jedničku by mohl být výsledek "0123", pro dvojku "0124" atd. Je žádán převod oběma směry. Tj. např. 1 = "0123", "0123" = 1. Číslo "123" v osmičkové soustavě sobě převedu na kód "0123" pochopitelně snadno. Kódy "0000" nebo "1212" jsou neplatné, neboť číslice se opakují.

Připomíná vám to některý matematický problém, o kterém já nevím?

(Líbí se mi totiž představa, že by se o převod staralo např. jen několik málo výrazů. Jinak počítám, že na to budu muset jít algoritmem, v tuto chvíli ještě nevím přesně jak, ale nějakým způsobem asi vytvořím v paměti seznam oněch unikátních kódů, index v seznamu rovná se tomu přirozenému číslu, převod opačným směrem probíhá vyhledáváním).

Třeba jste chytří a budete to někdo vědět ;) Díky za radu. M.

Citovat příspěvek

 

 

 

Přihlášení k mému účtu

Uživatelské jméno:

Heslo: