Losowo występujący błąd

Program ma takie dwa fragmenty:

     int m=(int)C(rozmiar*rozmiar,rozmiar); //symbol Newtona (=19 477 92)
     for(int i=0;i<testy;i++)
     {
            losuj3(m);
     }

Zmienne rozmiar i testy wpisuje użytkownik (tzn. ja). Wpisywałem rozmiar = 6, oraz testy rzędu kilka tysięcy.

    private void losuj3(int m)
    {
        liczby=new int[rozmiar][rozmiar];
        int[] temp=new int[rozmiar*rozmiar];
        long l=1+losowacz3.nextInt(m);
        //l=10626L; //ignoruję wynik losowania, liczę dla liczby, która poprzednio generowała błąd.
        long s=0;
        int n=rozmiar*rozmiar-1;
        int k=rozmiar-1;
        long poprzednia=0;
        for(int i=0;i<rozmiar;i++)
        {
            int liczba=0;
            while(s<l)
            {
                 poprzednia=s;
                 s+=C(n,k);
                 n--;
             }
             liczba=rozmiar*rozmiar-n-1;
             temp[liczba-1]=1;

             l-=poprzednia;
             n=rozmiar*rozmiar-liczba-1;
             s=0;
             poprzednia=0;
             k--;
        }
    }

Dla niezorientowanych: funkcja losuj3() losuje liczbę l z zakresu 1 - C(36,6), a następnie ustala jaki 6-elementowy podzbiór zbioru {1,2,...,36) znajduje się na pozycji l w uporządkowaniu leksykograficznym.
Dla dużych wartości zmiennej testy dla kilku spośród wylosowanych liczb wyniki są absurdalne. Hipoteza, że algorytm jest niepoprawny i dla tych liczb daje złe wyniki jest nieprawdziwa. Jeżeli po błędnym przebiegu zmienię program, zignoruję wynik losowania i liczę dla liczb generujących poprzednio błąd, to wyniki są prawidłowe.
Widzi ktoś błąd?

Cześć ;-)

        int n=rozmiar*rozmiar-1;
        [...]
        [...]
        for(int i=0;i<rozmiar;i++)

"i" wędruje od zera do rozmiar^2 - 2, tak ma być?

X

Chyba jednak wedruje <0; rozmiar).

@dr.Czepialski, nie rozumiem.

  for(int i=0;i<rozmiar;i++)

"i" wędruje od 0 do rozmiar-1.
Dodam jeszcze, że przy żadnym uruchomieniu w trybie debugowania (Eclipse) błąd nie wystąpił.

zrob jakies logi ze zmiennymi i do tego w kilku punktach algorytmu a nastepnie przesledz :)

@mgs_saladin, ciekawy pomysł ale przecież napisałem:

Jeżeli po błędnym przebiegu zmienię program, zignoruję wynik losowania i liczę dla liczb generujących poprzednio błąd, to wyniki są prawidłowe.

Jak myślisz skąd wiem dla jakich wartości wystąpił błąd? Podpowiadam, skorzystałem z logów.

no fakt zapodaj ta funkcje "C" no i przy okazji "losowacz"? :)

   losowacz = new Random();
   .....
    private long C(int n,int k)
    {
        double wynik=1.0;
        int i=1;
        int ile=k;
        while(ile>0)
        {
            wynik*=((double)n)/i;
            n--;
            i++;
            ile--;
        }
        return (long)wynik;
    }

Ilość kombinacji jest liczona tak: C(n,k) = (n/1)((n-1)/2)((n-2)/3)*..., aby uniknąć pojawiania się dużych liczb.

java.lang.ArrayIndexOutOfBoundsException: 122010

hmm blad?

Na skutek czasami błędnego działania tej pętli

            while(s<l)
            {
                 poprzednia=s;
                 s+=C(n,k);
                 n--;
             }

zmienna n ma złą wartość, w konsekwencji zmienna liczba ma złą wartość i wierszu

    temp[liczba-1]=1;

jest przekroczeniu zakresu.
Posumowanie: w większości przypadków wspomniana pętla działa dobrze, czasami (dla tych samych wartości startowych) działa źle.

Dzięki za zainteresowanie. Z moich obserwacji (zgodnych z Twoimi) wynika, że czasami (zjawisko niepowtarzalne!) pętla

            while(s<l)  
            {
                 poprzednia=s;
                 s+=C(n,k);
                 n--;
            }

daje złą wartość zmiennej n, ale, niestety, wyliczona na jej podstawie wartość zmiennej liczba jest co prawda zła ale mieści się w zakresie dopuszczalnych indeksów. W konsekwencji instrukcja

   temp[liczba-1]=1;

nie rzuca wyjątkiem => nie wiadomo że błąd wystąpił => informacja o błędzie nie jest zapisywana do logu (wypisywana na ekran). Drugi przebieg pętli (z błędną wartością zmiennej n) produkuje już absurdalną wartość zmiennej liczba, i można obejrzeć informację o błędzie na ekranie (w pliku z logiem).
Wczoraj miałem przypadki, że już pierwszy przebieg pętli tworzył zupełnie złą wartość zmiennej liczba, dzisiaj jeszcze na to nie trafiłem.

juz wiem :) po prostu wydaje mi sie ze male omskniecie w logu tak patrzyłem sie dlaczego podając ta sama liczbę inny wynik jest :) po prostu ta liczba która powodowała blad teraz jest juz inna :)

przeanalizuj ten kod 3 liczby zakomentowane wyrzucają blad:

import java.util.Random;
import javax.swing.JApplet;

public class Test78_losowyBlad extends JApplet{

    @Override public void start(){
        System.out.println("start");
        int m=(int)C(rozmiar*rozmiar,rozmiar); //symbol Newtona (=19 477 92)
        for(int i=0;i<testy;i++)   {   losuj3(m);   }
        System.out.println("stop");
    }
 final int rozmiar=6;
 final int testy=15000;
 Random losowacz3 = new Random();

private void losuj3(int m)
{
        int[] temp=new int[rozmiar*rozmiar];
        long l=1+losowacz3.nextInt(m);
        System.out.println("====================> "+l);

        // l=1904664L;
        // l=1640154L;
        // l=226352L;

        long s=0;
        int n=rozmiar*rozmiar-1;
        int k=rozmiar-1;
        long poprzednia=0;
          for(int i=0;i<rozmiar;i++)
          {
            int liczba=0;
            while(s<l)  {
                 poprzednia=s;
                 s+=C(n,k);
                 n--;
            }
            liczba=rozmiar*rozmiar-n-1;
            temp[liczba-1]=1;
            l-=poprzednia;

             n=rozmiar*rozmiar-liczba-1;
             s=0;
             poprzednia=0;
             k--;
            for(int xx=0;xx<rozmiar*rozmiar;xx++)
            {
                System.out.print("|"+temp[xx]);
            }
            System.out.println(">");
            System.out.println("_____________________");
          }
}

private long C(int n,int k) {
        double wynik=1.0;
        int i=1;
        int ile=k;
     //   System.out.println("k="+k+" n="+n);
        while(ile>0)
        {
            wynik*=((double)n)/i;
            n--;
            i++;
            ile--;
        }
        return (long)wynik;
}
}

Błąd jednak nie był losowy.
Fragment

            while(s<l)  
           {
                 poprzednia=s;
                 s+=C(n,k);
                 n--;
            }

należy zastąpić takim

            while(s<l && n>=k)  
           {
                 poprzednia=s;
                 s+=C(n,k);
                 n--;
            }