[informatica] java: permutatie van 2 rijen, eenvoudiger?

Moderators: ArcherBarry, Fuzzwood

Reageer

Bericht 17-01-'13, 10:48

Kwintendr

Gebruikersavatar
Berichten: 768

java: permutatie van 2 rijen, eenvoudiger?

Hallo iedereen,

De opdracht luidt als volgt: Je krijgt 2 rijen. Is de ene een permutatie van de andere. Ik heb hiervoor een programma geschreven, maar ik vind het nogal vrij complex voor wat het uiteindelijk maar moet doen. Alleen vind ik geen eenvoudigere methode. Toch zou ik graag een eenvoudigere methode hebben als die bestaat, kwestie van ook op het examen efficiënter te werk te kunnen gaan. Dit is mijn code:

Code: Selecteer alles

public class permutatiesnietcyclisch {

/**

  * @param args

  */

public static void main(String[] args) {

  int[] rij1 = { 2,1,4,5,3};

  int[] rij2 = { 5,4,2,3,1};

  permutatiesnietcyclisch.test(rij1, rij2, 6);

}

static public void test(int[] rij1, int[] rij2, int N) {

  boolean[] rij11 = new boolean[rij1.length];

  boolean[] rij22 = new boolean[rij2.length];

  if ((rij1.length == rij2.length) && (rij1.length < N)) {

   for (int i = 0; i < rij1.length; i++) {

boolean a = false;

int teller = 0;

for (int j = 0; j < rij1.length; j++) {

 if ((rij1[i] == rij2[j]) && (teller == 0)) {

  teller = teller + 1;

  a = true;

 } else if ((teller == 1) && (a == true)) {

  a = true;

 } else {

  a = false;

 }

}

rij22[i] = a;

teller = 0;

for (int j = 0; j < rij1.length; j++) {

 if ((rij1[i] == rij1[j]) && (teller == 0)) {

  teller = teller + 1;

  rij11[i] = true;

 } else if ((teller == 1) && (rij1[i] == rij1[j])) {

  rij11[i] = false;

 } else if ((teller == 1) && (rij1[i] != rij1[j])) {

  rij11[i] = true;

 } else {

  rij11[i] = false;

 }

}

   }

   boolean z = false;

   for (int i = 0; i < rij11.length; i++) {

if (rij11[i] == rij22[i]) {

 z = true;

} else {

 i = rij11.length;

 z = false;

}

   }

   System.out.println(z);

  } else {

   System.out.println("Foute invoer!");

  }

}

}
Het Wetenschapsforum heeft ook een facebook pagina!
Omhoog

Bericht 17-01-'13, 11:03

Xenion

Gebruikersavatar
Berichten: 2.609

Re: java: permutatie van 2 rijen, eenvoudiger?

Wat bedoel je juist met een permutatie en niet cyclisch?

Gewoon: "bevat dezelfde elementen maar niet noodzakelijk in dezelfde volgorde"?
Omhoog

Bericht 17-01-'13, 11:06

Kwintendr

Gebruikersavatar
Berichten: 768

Re: java: permutatie van 2 rijen, eenvoudiger?

Naar de naam moet je niet kijken, ik had al iets met permutaties gedaan en die waren cyclisch. Dat had ik gewoon permutatie genoemd. Ik moest dus een andere naam hebben en dat is het geworden :)
Het Wetenschapsforum heeft ook een facebook pagina!
Omhoog

Bericht 17-01-'13, 11:20

Xenion

Gebruikersavatar
Berichten: 2.609

Re: java: permutatie van 2 rijen, eenvoudiger?

Ok, maar is dit wat je wil: "bevat dezelfde elementen maar niet noodzakelijk in dezelfde volgorde"?

In dat geval zou ik het volgende doen:

Code: Selecteer alles


ALS lengte(l1) != lengte(l2)

  return false

Maak een nieuwe lijst met de naam 'gevonden'.

Loop met i over l1

  Loop met j over l2

ALS l1(i) == l2(j)

  ALS j in gevonden, doe niks

  ANDERS

    voeg j toe aan gevonden

break;

ANDERS

  als j het einde van lijst 2 was en je hebt l1(i) nog niet gevonden, dan is het geen permutatie

  return false
Als je op het einde van die functie geraakt dan was het een permutatie. Als het geen permutatie is dan zal je onderweg al false gereturned hebben.
Omhoog

Bericht 17-01-'13, 11:28

Kwintendr

Gebruikersavatar
Berichten: 768

Re: java: permutatie van 2 rijen, eenvoudiger?

Xenion schreef: ↑do 17 jan 2013, 11:20
Ok, maar is dit wat je wil: "bevat dezelfde elementen maar niet noodzakelijk in dezelfde volgorde"?
ja, dat is de bedoeling.

Jij doet het nu met lijsten, dat is perfect mogelijk, maar stel nu dat je het alleen moet doen mijn rijen, dus zonder gebruik te maken van lijsten.
Het Wetenschapsforum heeft ook een facebook pagina!
Omhoog

Bericht 17-01-'13, 11:42

Xenion

Gebruikersavatar
Berichten: 2.609

Re: java: permutatie van 2 rijen, eenvoudiger?

Voor de l1 en l2 is er geen verschil. Ik bedoelde ook eigenlijk rij. Als je een list mag gebruiken is het nog eenvoudiger, want daar kan je gewoon de elementen die je al gevonden hebt paarsgewijs schrappen en kijken of je op het einde 2 lege lijsten overhoudt.

Voor de 'gevonden' lijst kan je ook een rij gebruiken. Je weet immers op voorhand hoeveel elementen daar maximum in zullen zitten (namelijk het aantal elementen in de gegeven rijen). Je weet ook steeds tot waar de rij al 'gevuld' is. Als je het i'de element van l1 aan het zoeken bent in l2 dan heb je op dat moment i-1 elementen gevonden.
Omhoog

Bericht 17-01-'13, 11:50

EvilBro

Berichten: 7.068

Re: java: permutatie van 2 rijen, eenvoudiger?

ik denk dat je te snel begint met programmeren. In mijn ogen zou je eerst pseudocode moeten schrijven (iets wat Xenion hierboven doet) zodat je je algoritme duidelijker voor ogen hebt. In dit geval zou ik gaan voor:

- sorteer lijst 1 van laag naar hoog

- sorteer lijst 2 van laag naar hoog

- zijn de twee gesorteerde lijsten aan elkaar gelijk.

Het sorteren doe je dan in een aparte functie. Hierdoor wordt je code zeer overzichtelijk. Iedereen die het hoofdprogramma ziet kan meteen zien dat wat je doet klopt.

Code: Selecteer alles

	public static void main(String[] args) {

		int[] rij1 = {1,2,3,4};

		int[] rij2 = {1,3,2,4};



		System.out.println(rijenGelijk(sort(rij1),sort(rij2)));

	}

	

	public static int[] sort(int[] rij) {

	}

	

	public static boolean rijenGelijk(int[] rij1, int[] rij2) {

	}
Deze methode heeft bovendien nog een extra voordeel. Stel dat je later een sneller sorteeralgoritme verzint. Je hoeft dan alleen de code in sort aan te passen.
Omhoog

Bericht 17-01-'13, 18:35

Kwintendr

Gebruikersavatar
Berichten: 768

Re: java: permutatie van 2 rijen, eenvoudiger?

Ik heb nooit gewerkt met een pseudo code, maar ik moet zeggen dat alles zo wel vlotter verloopt. Alleen zit ik vast bij mijn sorteer-methode. Bij de rij {1,2,3,4} geeft hij 1,2,3,4. Maar bij de rij {4,3,2,1} Geeft hij 1,1,1,1.

Dit is mijn sorteercode:

Code: Selecteer alles

 static public int[] sorteerrij(int[] a) {

  int min = a[0];

  int z = 0;

  for (int i = 0; i < a.length; i++) {

   for (int j = i; j < a.length; j++) {

min = a[i];

if (min >= a[j]) {

 min = a[j];

 z = i;

}

   }

   System.out.println(min);

   a[z] = a[0];

   a[0] = min;

   z = 0;

  }

  return a;

}
Ik snap niet wat er fout is, ik heb de code ook al eens overlopen met pen en papier.
Het Wetenschapsforum heeft ook een facebook pagina!
Omhoog

Bericht 17-01-'13, 19:54

Typhoner

Gebruikersavatar
Berichten: 2.455

Re: java: permutatie van 2 rijen, eenvoudiger?

wil je niet z=j stellen?
This is weird as hell. I approve.
Omhoog

Bericht 17-01-'13, 20:13

Kwintendr

Gebruikersavatar
Berichten: 768

Re: java: permutatie van 2 rijen, eenvoudiger?

Ja inderdaad, die z moet gelijk gesteld worden aan j ipv i, bedankt!

Ik heb er ondertussen nog wat fouten uit gehaald uit dat stukje :roll: :

Code: Selecteer alles

min = a[i];
moet boven de for-lus met j staan en

Code: Selecteer alles

a[z] = a[0];
moet

Code: Selecteer alles

a[z] = a[i];
worden en

Code: Selecteer alles

a[0] = min;
moet

Code: Selecteer alles

a[i] = min;
worden
Het Wetenschapsforum heeft ook een facebook pagina!
Omhoog

Bericht 17-01-'13, 21:24

Typhoner

Gebruikersavatar
Berichten: 2.455

Re: java: permutatie van 2 rijen, eenvoudiger?

aaaaah, programmeren.... geen enkele manier om meer fouten te maken in zo weinig tijd :D
This is weird as hell. I approve.
Omhoog

Bericht 17-01-'13, 23:15

EvilBro

Berichten: 7.068

Re: java: permutatie van 2 rijen, eenvoudiger?

Mijn variant:

Code: Selecteer alles

	public static int[] sort(int[] rij) {

		for (int i = 0; i < rij.length-1; i++) {

			int minIndex = i;

			for (int j = i+1; j < rij.length; j++) {

				if (rij[j] < rij[minIndex]) {

					minIndex = j;

				}

			}

			int dummy = rij[minIndex];

			rij[minIndex] = rij[i];

			rij[i] = dummy;

		}

		return rij;

	}
Omhoog
Reageer

Terug naar “Huiswerk en Practica”