[JAVA] La Bandiera Tricolore

[life_is_a_bitch]

Salve a tutti,
volevo proporvi un classico degli esercizi che si svolgono in un corso di programmazione java...

Dato un array di interi, si crei un metodo void bandiera(int [] a) che suddivida tale array in tre parti senza usare array di appoggio.
una parte con gli int che %3 danno resto 0, un'altra con quelli che danno resto 1 e la restante con quelli che danno resto 2.

Dovendo realizzare un metodo boolean testBandiera(int[] a) che verifichi la reale suddivisione dell'array nelle tre parti sopracitate, come lo fareste?
a me per ora non vengono in mente soluzioni brillanti...
a voi la parola ! e grazie preventivamente dell'aiuto

[andbin]

Originariamente inviato da life_is_a_bitch

Dato un array di interi, si crei un metodo void bandiera(int [] a) che suddivida tale array in tre parti senza usare array di appoggio.
una parte con gli int che %3 danno resto 0, un'altra con quelli che danno resto 1 e la restante con quelli che danno resto 2.

Chiaramente bisognerebbe fissare delle condizioni sulle caratteristiche dell'array in input. E cioè che l'array sia lungo un multiplo di 3 e che ci sia un numero corretto di valori per ognuna delle tre parti (per fare un esempio, se l'array è lungo 9 non ci possono essere 4 elementi per cui %3 = 0).
Dico bene?

[Gica78R]

Originariamente inviato da andbin

Chiaramente bisognerebbe fissare delle condizioni sulle caratteristiche dell'array in input. E cioè che l'array sia lungo un multiplo di 3 e che ci sia un numero corretto di valori per ognuna delle tre parti (per fare un esempio, se l'array è lungo 9 non ci possono essere 4 elementi per cui %3 = 0).
Dico bene?

Non mi sembra che ci sia un vincolo che impone che le tre parti dell'array debbano essere della stessa dimensione, quindi l'array può essere di qualunque dimensione e, in teoria, contenere anche solo valori multipli di 3, che quindi occuperanno tutto l'array...

[morskott]

Io risolverei così

public class Bandiera{
	public static void bandiera(int[] a){
		bandiera(a,0);
	}

	private static void bandiera(int[] a,int index){
		if (index==a.length) return;
		else{
			if (a[index]%3==0) mettiSinistra(a,index);
			if (a[index]%3==2) mettiDestra(a,index);
			bandiera(a,index+1);
		}
	}

	private static void mettiDestra(int[] a,int index){
		int temp=a[a.length-1];
		a[a.length-1]=a[index];
		a[index]=temp;
	}

	private static void mettiSinistra(int[] a,int index){
		int temp=a[0];
		a[0]=a[index];
		a[index]=temp;
	}

	public static boolean testBandiera(int[] a){
		return testBandiera(a,0,0);
	}

	private static boolean testBandiera(int[] a,int index,int mode){
		if (a.length==index) return true;
		else
		if (mode==3) return false;
		else{
			return a[index]%3==mode && (testBandiera(a,index+1,mode) || testBandiera(a,index+1,mode+1));
		}
	}
}

[andbin]

Originariamente inviato da Gica78R

Non mi sembra che ci sia un vincolo che impone che le tre parti dell'array debbano essere della stessa dimensione, quindi l'array può essere di qualunque dimensione e, in teoria, contenere anche solo valori multipli di 3, che quindi occuperanno tutto l'array...

E allora, scusa, che "bandiera" sarebbe??

Comunque io ho solo fatto una domanda/precisazione e l'unico che può rispondere/confermare è life_is_a_bitch. Per me potrebbe andare bene tanto la "mia" specifica quanto la "tua".

[mad_hhatter]

Originariamente inviato da morskott

Io risolverei così

public class Bandiera{
	public static void bandiera(int[] a){
		bandiera(a,0);
	}

	private static void bandiera(int[] a,int index){
		if (index==a.length) return;
		else{
			if (a[index]%3==0) mettiSinistra(a,index);
			if (a[index]%3==2) mettiDestra(a,index);
			bandiera(a,index+1);
		}
	}

	private static void mettiDestra(int[] a,int index){
		int temp=a[a.length-1];
		a[a.length-1]=a[index];
		a[index]=temp;
	}

	private static void mettiSinistra(int[] a,int index){
		int temp=a[0];
		a[0]=a[index];
		a[index]=temp;
	}

	public static boolean testBandiera(int[] a){
		return testBandiera(a,0,0);
	}

	private static boolean testBandiera(int[] a,int index,int mode){
		if (a.length==index) return true;
		else
		if (mode==3) return false;
		else{
			return a[index]%3==mode && (testBandiera(a,index+1,mode) || testBandiera(a,index+1,mode+1));
		}
	}
}

può essere che mi sbagli, ma non è errato? se ho questo array {0, 1, 1, 0} arrivato all'ultimo elemento, scambia i due zeri e basta... invece di scambiare i 2 elementi, mettiDestra e mettiSinistra dovrebbero fare spazio e infilare l'elemento rispettivamento in a[length-1], a[0]... ripeto: sempre che non mi sia perso qualche passaggio

[morskott]

Originariamente inviato da mad_hhatter

può essere che mi sbagli, ma non è errato? se ho questo array {0, 1, 1, 0} arrivato all'ultimo elemento, scambia i due zeri e basta... invece di scambiare i 2 elementi, mettiDestra e mettiSinistra dovrebbero fare spazio e infilare l'elemento rispettivamento in a[length-1], a[0]... ripeto: sempre che non mi sia perso qualche passaggio

Mo sull'array che dici tu devo ancora pensare, ma la mia idea è, se è %3=0 sta tutto a sinistra, %3=2 tutto a destra, cioè, se in qualsiasi pos dell'array trovo un elem che %3=0 lo metto nella prima posizione di sin, se %3=2 lo metto nell'ultima posizione a destra e implicitamente alla fine quelli %3=1 saranno in mezzo

EDIT:Hai ragione, dovrei fare uno scalamento progressivo su tutti gli elem dell'array

EDIT2:
Ecco la versione corretta (spero)

public class Bandiera{
	public static void bandiera(int[] a){
		bandiera(a,0);
	}

	private static void bandiera(int[] a,int index){
		if (index==a.length) return;
		else{
			if (a[index]%3==0) mettiSinistra(a,index);
			if (a[index]%3==2) mettiDestra(a,index);
			bandiera(a,index+1);
		}
	}

	private static void mettiDestra(int[] a,int index){
		int temp=a[index];
		for (int i=a.length-1;i>index;i--)
			a[i-1]=a[i];
		a[a.length-1]=temp;
	}

	private static void mettiSinistra(int[] a,int index){
		int temp=a[index];
		for (int i=0;i<index;i++)
			a[i+1]=a[i];
		a[0]=temp;
	}

	public static boolean testBandiera(int[] a){
		return testBandiera(a,0,0);
	}

	private static boolean testBandiera(int[] a,int index,int mode){
		if (a.length==index) return true;
		else
		if (mode==3) return false;
		else{
			return a[index]%3==mode && (testBandiera(a,index+1,mode) || testBandiera(a,index+1,mode+1));
		}
	}
}

[wingman87]

Io farei una specie di bubble sort:
inizia la ricerca, se trovo un %3=0 lo porto su finchè non trovo la cima o un altro %3=0, se trovo un %3=1 lo porto su finchè non trovo un %3=1 o un %3=0 o la cima, se trovo un %3=2 lo lascio dov'è...
E per la verifica basta scorrere l'array, se trovo blocchi di numeri dello stesso tipo in posti differenti allora ritorno false

[andbin]

Innanzitutto premetto che come "specifiche" mi va anche bene quando detto da Gica78R, cioè che non ci siano vincoli sulla lunghezza dell'array o sulla ripartizione dei valori.

Detto questo mi permetto di postare la "mia" versione:

import java.util.*;

public class Prova
{
    public static void main (String[] args)
    {
        int[] arr;

        arr = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
        System.out.println ("prima: " + Arrays.toString (arr));
        bandiera (arr);
        System.out.println ("dopo:  " + Arrays.toString (arr));

        arr = new int[] { 3, 2, 4, 6, 9, 8, 10 };
        System.out.println ("prima: " + Arrays.toString (arr));
        bandiera (arr);
        System.out.println ("dopo:  " + Arrays.toString (arr));
    }

    public static void bandiera (int[] a)
    {
        for (int i=0, k=0; i < 3; i++)
        {
            for (int j=k; j < a.length; j++)
            {
                if (a[j] % 3 == i)
                {
                    int t = a[k];
                    a[k++] = a[j];
                    a[j] = t;
                }
            }
        }
    }
}

L'output è:

prima: [0, 1, 2, 3, 4, 5, 6, 7, 8]
dopo:  [0, 3, 6, 1, 4, 7, 2, 5, 8]
prima: [3, 2, 4, 6, 9, 8, 10]
dopo:  [3, 6, 9, 4, 10, 8, 2]

Come potete vedere, l'algoritmo che ho usato è davvero molto semplice, lineare e pulito e, almeno per me, ricorda molto il bubble-sort.
L'unica cosa è che non è "stable" cioè non mantiene l'ordine relativo degli elementi (si noti che nel secondo test 2 e 8 vengono scambiati come ordine).

Se lo volete "stable", beh, ci debbo pensà.....

[mad_hhatter]

Originariamente inviato da andbin

Innanzitutto premetto che come "specifiche" mi va anche bene quando detto da Gica78R, cioè che non ci siano vincoli sulla lunghezza dell'array o sulla ripartizione dei valori.

Detto questo mi permetto di postare la "mia" versione:

import java.util.*;

public class Prova
{
    public static void main (String[] args)
    {
        int[] arr;

        arr = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
        System.out.println ("prima: " + Arrays.toString (arr));
        bandiera (arr);
        System.out.println ("dopo:  " + Arrays.toString (arr));

        arr = new int[] { 3, 2, 4, 6, 9, 8, 10 };
        System.out.println ("prima: " + Arrays.toString (arr));
        bandiera (arr);
        System.out.println ("dopo:  " + Arrays.toString (arr));
    }

    public static void bandiera (int[] a)
    {
        for (int i=0, k=0; i < 3; i++)
        {
            for (int j=k; j < a.length; j++)
            {
                if (a[j] % 3 == i)
                {
                    int t = a[k];
                    a[k++] = a[j];
                    a[j] = t;
                }
            }
        }
    }
}

L'output è:

prima: [0, 1, 2, 3, 4, 5, 6, 7, 8]
dopo:  [0, 3, 6, 1, 4, 7, 2, 5, 8]
prima: [3, 2, 4, 6, 9, 8, 10]
dopo:  [3, 6, 9, 4, 10, 8, 2]

Come potete vedere, l'algoritmo che ho usato è davvero molto semplice, lineare e pulito e, almeno per me, ricorda molto il bubble-sort.
L'unica cosa è che non è "stable" cioè non mantiene l'ordine relativo degli elementi (si noti che nel secondo test 2 e 8 vengono scambiati come ordine).

Se lo volete "stable", beh, ci debbo pensà.....

molto bello, bravo!
per renderlo stabile, la mia versione (verisone di moskott modificata) risulta stabile se l'inserimento a destra inserisce nell'ultima posizione, mentre l'inserimento a sinistra inserisce a destra dell'area A,
dove làarea A eà la parte sinistra dell'array e tale che i suoi elementi sono divisibili per 3

pero' a occhio la complessita' e' maggiore della tua soluzione

[71104]

Originariamente inviato da andbin

E cioè che l'array sia lungo un multiplo di 3

e perché? anche un array da 4 locazioni può essere diviso in tre parti, per esempio le prime due locazioni, la successiva, e la successiva ancora. piuttosto dovrebbe verificare che la lunghezza sia maggiore o uguale a 3.

e che ci sia un numero corretto di valori per ognuna delle tre parti (per fare un esempio, se l'array è lungo 9 non ci possono essere 4 elementi per cui %3 = 0).

perché?

[andbin]

Originariamente inviato da mad_hhatter

molto bello, bravo!

Grazie.

Una implementazione "stable" si può fare in questo modo:

public static void bandiera (int[] a)
{
    for (int i = 0; i < a.length-1; i++)
    {
        for (int j = i+1; j < a.length; j++)
        {
            int mi = a[i] % 3;
            int mj = a[j] % 3;

            if (mi > mj || (mi == mj && a[i] > a[j]))
            {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
    }
}

Questo è un "vero" bubble-sort, solo con il test tra i due elementi un po' particolare.

Un esempio è questo:

prima: [9, 6, 10, 7, 4, 1, 14, 11, 5, 2]
dopo:  [6, 9, 1, 4, 7, 10, 2, 5, 11, 14]

Tuttavia il bubble-sort ha una complessità decisamente maggiore rispetto alla implementazione che ho postato prima.

Originariamente inviato da 71104

e perché? anche un array da 4 locazioni può essere diviso in tre parti, per esempio le prime due locazioni, la successiva, e la successiva ancora. piuttosto dovrebbe verificare che la lunghezza sia maggiore o uguale a 3.

perché?

Calma ... era solo un mio "dubbio".