[es] - Permutacije bez ponavljanja??

river
System Architect

Član broj: 12566
Poruke: 62
213.244.197.*

+1 Profil

^{14.02.2006. u 11:27 - pre 221 meseci}

Evo ti parče koda koji ja koristim. U formi je iteratora tako da je lako za korišćenje, jedino je bitno zapamtiti da je return iz next() metode Object[] te treba kastovati ispravno.

Code:

import java.util.Iterator;
public class Permutations implements Iterator {
    protected Object[] inArray;
    protected int n, m;
    protected int[] index;
    protected boolean hasMore = true;

    public Permutations(Object[] inArray) throws Exception {

        this(inArray, inArray.length);
    }

    public Permutations(Object[] inArray, int m) throws Exception {

        this.inArray = inArray;
        this.n = inArray.length;
        this.m = m;

        // throw exception unless n >= m >= 0
        if (n < 0) {
            throw new Exception(
                "n, the number of items, must be " +
                "greater than 0");
        }
        if (n < m) {
            throw new Exception(
                "n, the number of items, must be >= m, "+
                "the number selected");
        }
        if (m < 0) {
            throw new Exception(
                "m, the number of selected items, must be >= 0");
        }

        index = new int[n];
        for (int i = 0; i < n; i++) {
            index[i] = i;
        }

        reverseAfter(m - 1);
    }

    public boolean hasNext() {
        return hasMore;
    }

    protected void moveIndex() {

        int i = rightmostDip();
        if (i < 0) {
            hasMore = false;
            return;
        }

        int leastToRightIndex = i + 1;
        for (int j = i + 2; j < n; j++) {
            if (index[j] < index[leastToRightIndex] && index[j] > index[i]) {
                leastToRightIndex = j;
            }
        }

        int t = index[i];
        index[i] = index[leastToRightIndex];
        index[leastToRightIndex] = t;

        if (m - 1 > i) {
            reverseAfter(i);
            reverseAfter(m - 1);
        }

    }

    public Object next() {
        if (!hasMore) {
            return null;
        }

        Object[] out = new Object[m];
        for (int i = 0; i < m; i++) {
            out[i] = inArray[index[i]];
        }

        moveIndex();
        return out;
    }

    protected void reverseAfter(int i) {

        int start = i + 1;
        int end = n - 1;
        while (start < end) {
            int t = index[start];
            index[start] = index[end];
            index[end] = t;
            start++;
            end--;
        }

    }

    protected int rightmostDip() {
        for (int i = n - 2; i >= 0; i--) {
            if (index[i] < index[i + 1]) {
                return i;
            }
        }
        return -1;

    }

    public void remove() {
        throw new UnsupportedOperationException();
    }
}

_{[Ovu poruku je menjao river dana 14.02.2006. u 12:30 GMT+1]}

Everything should be made as simple as possible, but not simpler. - AA

Odgovor na temu

Java Beograd
Novi Beograd

Član broj: 11890
Poruke: 9513
*.lukoil.co.yu.

+10254 Profil

Re: Permutacije bez ponavljanja??

^{14.02.2006. u 11:31 - pre 221 meseci}

Nema. Ali ...

Pojam "Javina biblioteka" je tesko definisati. Jer:
- Postoje biblioteke proizvodjaca Jave koje pocinju recju java. Na primer:
java.awt.event.
- Zatim postoje extend biblioteke proizvodjaca koje pocinju sa javax
- Zatim postoje biblioteke gde se proizvodjac ponasa kao nezavisni proizvodjac pa biblioteke pocinju sa: com.sun.
- I na kraju postoji mali milion nezavisnih proizvodjaca sa svojim bibliotekama. Neke su dž. a neke se kupuju.
- I na kraju krajeva postoji veliki milion biblioteka koje su razvijene kao "ne-profi", dakle, amateri, zaljubljenici, klinci i matorci, studenti, đaci, milicajci ...

Kad sam rekao "Nema", mislio sam na biblioteke koje pocinju sa java i javax.

Dakle, na Google pa traži. U 99% slučajeva ja sam iskopao šta mi je trebalo.

---------------------------------------------------------------------------
Evo, "river" je postovao dok sam ja kucao. Dakle, i to je sad necija biblioteka.

_{[Ovu poruku je menjao Java Beograd dana 14.02.2006. u 12:34 GMT+1]}

OTPOR blokadi ulica, OTPOR blokiranom Beogradu, OTPOR blokiranoj Srbiji

Odgovor na temu