Trucos de programacion para la loto

Responder
Indeciso
14
14
Mensajes: 5584
Registrado: Dom 10 Oct, 2004 8:26 pm

Trucos de programacion para la loto

Mensaje por Indeciso »

De mi despensa, hilo mio del otro foro (y luego por comodidad tengo cada truño, en casa del herrero...):

No son mios, son de Uros Boltin ->Ininuga:

http://www2.arnes.si/~ubolti/ininuga/

Counting Rare Bits

When working with wheels, you will frequently need to count the numbers in an intersection of two sets, i.e. in how many numbers they match. Typically, that is a small number of numbers. So when sets are represented as bitmaps, only a few bits are set to 1, most are 0. Here is a fast way to count them in such case.

Take a 32-bit example (call it x):
00010000010010000010000000000000

Subtract 1, you get:
00010000010010000001111111111111

Then, "x and (x-1)" is:
00010000010010000000000000000000

You have cut down one bit.

So, the following loop will count them all:

Count := 0;
while x<>0 do begin
x := x and (x-1);
Inc(Count);
end;

Or, even when set bits are not rare, you might wish only to check if their number is not above some limit:

for i:=1 to limit do x := x and (x-1);
if x=0 then...

In any case, the spent time is only proportional to the number of bits to count, not to the size of the whole set.



Making Bits Rare

When testing a wheel, e.g. C(16,6,4,5), you need to match a "way", e.g. W={2,4,6,7,8}, to a "game", e.g. G={1,2,3,4,6,7}. When these are stored as bitmaps (e.g. in left-to-right order here), you would have:
0101011100000000 (W)
1111011000000000 (G)

The intersection, containing 4 numbers {2,4,6,7}, would have 4 bits to count:
0101011000000000 (W and G)

Instead, you can store the "game" as inverse, i.e. set each bit to 0 if the number is in and to 1 if it's not:
0101011100000000 (W)
0000100111111111 (not G)

The intersection now only contains number 8, which is in W but not in G, so there is only 1 (=5-4) bit to count:
0000000100000000 (W and not G)

In general with C(v,k,t,m), there is typically t > m-t for most practically useful wheels, so using this inversion will speed up the testing, when you count bits as suggested above ("Counting Rare Bits").
Indeciso
14
14
Mensajes: 5584
Registrado: Dom 10 Oct, 2004 8:26 pm

Re: Trucos de programacion para la loto

Mensaje por Indeciso »

Combination Ordinal Numbers

A combination of numbers can be represented by literally listing the numbers, e.g. (1,2,3,4,6) or (1,2,3,4,5). An alternative way is to tell the combination's ordinal number in the list of all combinations of its size. E.g. the two combinations above are number 2 and number 1 respectively. The (6,8,9,10,11) and (7,8,9,10,11) are numbers 461 and 462, since they are the last two out of 5 from 11 and there are 462 of them all. For those in between, there is more than one way of how they can be ordered. Usually, the following two systems are used:

a) relative ordering (the usual lexicographic order)

b) absolute ordering (also called "combination sequence numbers" or CSN)

To compare them, see how 4 of 7 are listed in each case:

RELATIVE

1. 1,2,3,4
2. 1,2,3,5
3. 1,2,3,6
4. 1,2,3,7
5. 1,2,4,5
6. 1,2,4,6
etc.
ABSOLUTE

1. 1,2,3,4
2. 1,2,3,5
3. 1,2,4,5
4. 1,3,4,5
5. 2,3,4,5
6. 1,2,3,6
etc.


Obviously, the relative ordinal numbers depend on the pool size (7 in this case). If the pool were bigger than 7, the combination number 5 would be (1,2,3,Cool rather than (1,2,4,5). This is not the case with absolute ordinals, where all combinations of e.g. 5 numbers are listed before number 6 is added. Or not added, if pool is 5. Makes no difference for combinations before. So an absolute ordinal number and the pick (4 here) alone uniquely determine the combination.

There are two separate cases in program Ininuga when ordinal numbers are calculated.
a) A separate "Convert Ordinals" dialog box can be opened to convert an individual combination. This box is intended to be used manually as a utility calculator for this purpose. (Within Ininuga's pool range 1..32; else see the link below.)
b) Ordinal numbers are also an option while displaying, exporting or importing the wheels.

To see the source code of the routines, used for this purpose, open:

Pascal & Assembler: the optimized working version. (Compare comments in assembler with Pascal only version below.)

Pascal only: included for documentation purpose, although working, but slower.

- - -

Link: To calculate relative ordinals (pool 30 and above) go to Martin Round's page

- - -

And here is an observation for anyone interested in calculating these numbers. There is a simple conversion between absolute and relative ordinals. Let's take combinations 4 from 9 for example.
E.g., Abs.Ord.(2,3,5,7) = 22
Replace this with (9+1-2, 9+1-3, 9+1-5, 9+1-7) = (8,7,5,3)
Rel.Ord.(3,5,7,Cool = 105
which is 126+1-22, with 126 being the total of 4 from 9.
(BTW: All those "+1" turn into "-1" in case of zero-based indexing.)
Indeciso
14
14
Mensajes: 5584
Registrado: Dom 10 Oct, 2004 8:26 pm

Re: Trucos de programacion para la loto

Mensaje por Indeciso »

El codigo en Pascal para lo ultimo (UFFF Pascal! q recuerdos!)

unit Ord_Pas;
(* contents of file ord_pas.pas, *)
(* pascal only version of file ordinals.pas *)
(* by Uros Boltin *)

{ Calculates ordinal numbers of combinations and vice versa. }
{ Numbers can be in range [1..32]. }

interface

const
MaxN: integer = 32;

type
Set31 = set of 0..31;
LotMap = LongInt;
{ Type LotMap is used for binary bitmaps of combinations. }
{ Use Set31 type conversion to access numbers. It's zero-based! }
{ E.g.: ... if (x-1) in Set31(Lot) then ... }
{ Here, 0 stands for 1, 1 for 2 etc. until 31 for 32 }
{ Warning: set of 1..32 won't work! It's shifted and takes 5 bytes. }
TPascalTriangle = array[ 1..32, -1..30 ] of LongInt;
PPascalTriangle = ^TPascalTriangle;

const
Triangle: PPascalTriangle = nil;

procedure MakeTriangle;
procedure FreeTriangle;
function Binomial( n,r:integer ): LongInt;

function Backwards( Lot:LotMap; n:integer ): LotMap;
function LotIndex( Lot:LotMap ): LongInt;
function LotAt( Index:LongInt; r:integer ): LotMap;

{ Functions LotIndex and LotAt are the ones which actually do the job. }
{ They work with zero-based absolute ordinals. }
{ The following four functions are simple wrappers around them. }
{ These work with the usual ordinals, starting 1,2,3... }

function AbsoluteOrdinal( Lot:LotMap ): LongInt;
function RelativeOrdinal( Lot:LotMap; n,r:integer ): LongInt;
function FromAbsolute( Index:LongInt; r:integer ): LotMap;
function FromRelative( Index:LongInt; n,r:integer ): LotMap;



implementation


procedure MakeTriangle;
{ initialization before any other function can be called }
var
i,j: integer;
begin
if Triangle<>nil then Exit;
New( Triangle );
for i := 1 to 32 do Triangle^[i,-1] := 0;
for j := 0 to 30 do Triangle^[1,j] := j+1;
for i := 2 to 32 do
for j := 0 to 32-i do
Triangle^[i,j] := Triangle^[i-1,j] + Triangle^[i,j-1];
end;

procedure FreeTriangle;
{ cleanup before end of program }
begin
if Triangle<>nil then Dispose( Triangle );
Triangle := nil;
end;

function Binomial( n,r:integer ): LongInt;
begin
case r of
0: Binomial := 1;
1: Binomial := n;
else Binomial := Triangle^[r,n-r];
end;
end;


function Backwards( Lot:LotMap; n:integer ): LotMap;
var
x:integer;
Result: Set31;
begin
Result := [];
for x:=0 to n-1 do
if x in Set31(Lot) then Include( Result, n-1-x );
{ if it were 1-based, not 0-based, it would be x --> n+1-x }
Backwards := LotMap(Result);
end;

function LotIndex( Lot:LotMap ): LongInt;
var
i,j,x: integer;
Index: LongInt;
begin
i := 1;
j := -1;
Index := 0;
for x:=0 to MaxN-1 do
if x in Set31(Lot) then begin
Index := Index + Triangle^[i,j];
Inc(i);
end
else Inc(j);
LotIndex := Index;
end;

function LotAt( Index:LongInt; r:integer ): LotMap;
var
i,j,x: integer;
Lot: Set31;
begin
Lot := [];
i := r;
j := MaxN-1-r;
x := MaxN-1;
while r>0 do begin
if Index < Triangle^[i,j] then Dec(j)
else begin
Include( Lot, x );
Index := Index - Triangle^[i,j];
Dec(i);
Dec(r);
end;
Dec(x);
end;
LotAt := LotMap(Lot);
end;


function AbsoluteOrdinal( Lot:LotMap ): LongInt;
begin
if Lot=0 then AbsoluteOrdinal := 0
else AbsoluteOrdinal := LotIndex(Lot) + 1;
end;

function RelativeOrdinal( Lot:LotMap; n,r:integer ): LongInt;
begin
if Lot=0 then RelativeOrdinal := 0
else RelativeOrdinal := Binomial(n,r) - LotIndex( Backwards(Lot,n) );
end;

function FromAbsolute( Index:LongInt; r:integer ): LotMap;
begin
if Index=0 then FromAbsolute := 0
else FromAbsolute := LotAt( Index-1, r );
end;

function FromRelative( Index:LongInt; n,r:integer ): LotMap;
begin
if Index=0 then FromRelative := 0
else FromRelative := Backwards( LotAt( Binomial(n,r)-Index, r ), n );
end;

end.
Indeciso
14
14
Mensajes: 5584
Registrado: Dom 10 Oct, 2004 8:26 pm

Re: Trucos de programacion para la loto

Mensaje por Indeciso »

Pq puede q algun programador no lo entienda, voy a explicarlo:


Para un monton de operaciones necesitamos saber los numeros q llevamos en una apuesta y en otra, por ej para saber cuantos numeros tiene una combinacion de la ganadora, o a la hora de hacer una reduccion.

Si usas las herramientas del lenguaje de programacion literalmente te puedes morir...

ej: para una apuesta de 6 numeros, esta este numero en este conjunto.. y asi seis veces...

esto seria mortalmente lento.... necesitamos una estructura q nos permita hacer operaciones a nivel de bit...

dicho y hecho:
ej probando una combinacion C(16,6,4,5):

tengo mi apusta W={2,4,6,7,8}, y otra G={1,2,3,4,6,7}
los guardo como bitmaps de iz a de:

0101011100000000 (W)
1111011000000000 (G)

Para los despistados Wink -> hay un 1 en la posicion de cada numero, y necesito en este caso 16 bits pq son c(16,*;*;*)

La interseccion tiene 4 bits pq tiene 4 numeros en comun

0101011000000000 (W and G)


Y haces las operaciones " voladas", mientras q si haces comparaciones de numero a numero, o numero en un conjunto te puedes morir.

Para la reduccion igual:

Haces la interseccion a nivel de bit, y si (6 - n? de 1's q te quedan) >= reduccion (5,4,3) vas contando, para saber reductora.

Pd: Ya he puesto mi piedrecita para el lotofree, freeloto o como se llame Wink
Avatar de Usuario
Wandering
12
12
Mensajes: 1494
Registrado: Jue 26 Abr, 2018 8:50 pm

Re: Trucos de programacion para la loto

Mensaje por Wandering »

Pocos lo vamos a entender, sobre todo el empezar por la izquierda, lo normal es por la derecha, asi lo enseñan

Fenomenal la explicación.

:saludo: :beer2: :;):
:beer2: :money:
Indeciso
14
14
Mensajes: 5584
Registrado: Dom 10 Oct, 2004 8:26 pm

Re: Trucos de programacion para la loto

Mensaje por Indeciso »

Gracias Wandering ;)

Tambien ire poniendo (o poned) cosas que van bien para programa, por ej este texto de pacopuf, de como hacer un subir categoria

para una combinación de 6 números
>> obtengo un lista con las 6 combinaciones de 5 números que desarrolla
>> para cada una de las combinaciones de 5 números:
>>>> para cada uno de los números de 1 a 49
>>>>>> si el numero no esta en la combinación de 6
>>>>>>>> entonces lo añado a la combinación de 5, obteniendo una combinación de 6 que añado al resultado
>> al final tengo una lista con las 258 combinaciones buscadas
danvader99
11
11
Mensajes: 809
Registrado: Dom 29 Oct, 2017 8:20 pm

Re: Trucos de programacion para la loto

Mensaje por danvader99 »

si tienes razón haces las operaciones mas rápidas pero no "voladas"

serian voladas si hubiera una función que de esta comparación te sacara de golpe las coincidencias sin mas trabajando ella a nivel de maquina de forma trasparente

0101011100000000 (W)
1111011000000000 (G)

pero al final para hacer eso debes de usar algún bucle que recorra ambos bits, los compare etc, al menos en VBA, me imagino que en el resto de lenguajes era parecido

que si ,que es mas rápido , pero si tienes muchos datos necesitas que lo sea mucho mas

caca de ordenadores que tenemos y nos creemos que no, que es lo peor.


saludos
Responder