Springen naar inhoud

java: permutatie van 2 rijen, eenvoudiger?



  • Log in om te kunnen reageren

#1

Kwintendr

    Kwintendr


  • >250 berichten
  • 768 berichten
  • VIP

Geplaatst op 17 januari 2013 - 10:48

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:

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!

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 17 januari 2013 - 11:03

Wat bedoel je juist met een permutatie en niet cyclisch?

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

#3

Kwintendr

    Kwintendr


  • >250 berichten
  • 768 berichten
  • VIP

Geplaatst op 17 januari 2013 - 11:06

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!

#4

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 17 januari 2013 - 11:20

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

In dat geval zou ik het volgende doen:

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.

#5

Kwintendr

    Kwintendr


  • >250 berichten
  • 768 berichten
  • VIP

Geplaatst op 17 januari 2013 - 11:28

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!

#6

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 17 januari 2013 - 11:42

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.

#7

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 17 januari 2013 - 11:50

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.
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.

#8

Kwintendr

    Kwintendr


  • >250 berichten
  • 768 berichten
  • VIP

Geplaatst op 17 januari 2013 - 18:35

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:

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.

Veranderd door Kwintendr, 17 januari 2013 - 18:37

Het Wetenschapsforum heeft ook een facebook pagina!

#9

Typhoner

    Typhoner


  • >1k berichten
  • 2446 berichten
  • VIP

Geplaatst op 17 januari 2013 - 19:54

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

#10

Kwintendr

    Kwintendr


  • >250 berichten
  • 768 berichten
  • VIP

Geplaatst op 17 januari 2013 - 20:13

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: :

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

Veranderd door Kwintendr, 17 januari 2013 - 20:20

Het Wetenschapsforum heeft ook een facebook pagina!

#11

Typhoner

    Typhoner


  • >1k berichten
  • 2446 berichten
  • VIP

Geplaatst op 17 januari 2013 - 21:24

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

#12

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 17 januari 2013 - 23:15

Mijn variant:
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;
	}







Also tagged with one or more of these keywords: informatica

0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures