Springen naar inhoud

Bepaling index in een array


  • Log in om te kunnen reageren

#1

JackRnl

    JackRnl


  • 0 - 25 berichten
  • 15 berichten
  • Gebruiker

Geplaatst op 07 december 2007 - 18:03

Ik weet niet of ik HIER in de juiste rubriek zit. Indien niet dan 'sorry" (en verwijs me aub naar de juiste plaats)

Ik heb 3 (gehele) getallen waarvoor geldt
0< X < Y < Z < 10

Allereest wil ik de mogeljke combinaties op in een array:

dus:
index=0
for X = 1 to (10-2)
for Y = X+1 to (10-1)
for Z = Y+1 to 10
index=index+1
array(index,1)=X
array(index,2)=Y
array(index,3)=Z
next Z
next Y
next X

Vervolgens wil ik data in ander (lineair) array opslaan (ter grootte van "index") en terugzoeken op basis van de waarden van X, Y, Z.
Daartoe moet ik voor elke waarde die X, Y en Z hebben kunnen terugrekenen op welke positie het betreffende element wordt opgeslagen via iets als Index = GetIndex(X,Y,Z) (waarbij X, Y, Z bv 3, 6,8 zijn)

Het lijkt me dat dit een triviale vraag is, maar il vind het antdwoord niet.

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

#2

Fred F.

    Fred F.


  • >1k berichten
  • 4168 berichten
  • Pluimdrager

Geplaatst op 07 december 2007 - 21:39

Dit is geen triviale vraag.
Het antwoord is niet simpel: index = ...*X + ...*Y + ...*Z zoals jij waarschijnlijk hoopt. Je zilt een hele procedure moeten schrijven.

Overigens maak je hier fouten:

for X = 1 to (10-2)
for Y = X+1 to (10-1)
for Z = Y+1 to 10

Dat moet zijn:

for X = 1 to (10-3)
for Y = X+1 to (10-2)
for Z = Y+1 to (10-1)

Hydrogen economy is a Hype.

#3

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 08 december 2007 - 00:32

Het antwoord kan wel met een directe formule, maar je moet wat nare rijsommaties optellen om eraan te komen:

GetIndex(x,y,z)
{
  return z+((51-3*y)*y+(191+(x-24)*x)*x-270)/6;
}
In theory, there's no difference between theory and practice. In practice, there is.

#4

JackRnl

    JackRnl


  • 0 - 25 berichten
  • 15 berichten
  • Gebruiker

Geplaatst op 08 december 2007 - 08:51

Het antwoord kan wel met een directe formule, maar je moet wat nare rijsommaties optellen om eraan te komen:

GetIndex(x,y,z)
{
  return z+((51-3*y)*y+(191+(x-24)*x)*x-270)/6;
}


bedankt Rogier,

Kun je me wellicht ook de algemene formule geven (zodat ik die kan gebruiken indien het anatal niet 10 maar "N" is ?
bvd

Jack

#5

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 08 december 2007 - 10:27

Dat wordt dan zoiets:
GetIndex(x,y,z,n)
{
  return z+((11+(x+6)*x)*x)/6+((2*y+1-(x+4)*x+(x-1)*n)*n-(y+3)*y)/2;
}
In theory, there's no difference between theory and practice. In practice, there is.

#6

JackRnl

    JackRnl


  • 0 - 25 berichten
  • 15 berichten
  • Gebruiker

Geplaatst op 08 december 2007 - 11:11

Dat wordt dan zoiets:

GetIndex(x,y,z,n)
{
  return z+((11+(x+6)*x)*x)/6+((2*y+1-(x+4)*x+(x-1)*n)*n-(y+3)*y)/2;
}


Bedankt, het werkt!

Misschien een beetje teveel gevraagd, maar ik heb nog een vergelijkbaar probleempje
for x= 1 to N
for y =x+1 to N+1
for z =y+1 to N+2
pos =getindex(x,y,z,N)
next z
next y
next x

en teneinde mijn inzicht te vergroten:
waaruit bestaat de formule (hoe komt die tot stand)

nogmaals dank bij voorbaat

Veranderd door JackRnl, 08 december 2007 - 11:12


#7

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 08 december 2007 - 11:51

Bedankt, het werkt!

Misschien een beetje teveel gevraagd, maar ik heb nog een vergelijkbaar probleempje

Ik weet niet helemaal zeker wat je hier wilt, maar komt dit niet op hetzelfde neer als GetIndex(x,y,z,N+3) met de functie van hierboven?

en teneinde mijn inzicht te vergroten:
waaruit bestaat de formule (hoe komt die tot stand)

Het zijn een aantal somreeksen opgeteld, het getal wat je nodig hebt is eigenlijk het aantal combinaties (x,y,z) dat aan de gegeven (x,y,z) vooraf gaat. Dat aantal kun je opdelen in:
- het aantal (x,y,k) met y<k<z
- het aantal (x,k,?) met x<k<y en alle mogelijke z
- het aantal (k,?,?) met k<x en alle mogelijke y en z
Dat tweede aantal kun je schrijven als de som van alle aantallen (x,k,?) van k=x+1 t/m y-1
Dat derde aantal kun je schrijven als een som van aantallen van het tweede type.

Als je dan die somreeks uitwerkt en vereenvoudigt (hulpmiddelen toegestaan :D) krijg je bovenstaande formules.
In theory, there's no difference between theory and practice. In practice, there is.

#8

JackRnl

    JackRnl


  • 0 - 25 berichten
  • 15 berichten
  • Gebruiker

Geplaatst op 08 december 2007 - 17:04

Ik weet niet helemaal zeker wat je hier wilt, maar komt dit niet op hetzelfde neer als GetIndex(x,y,z,N+3) met de functie van hierboven?


Het zijn een aantal somreeksen opgeteld, het getal wat je nodig hebt is eigenlijk het aantal combinaties (x,y,z) dat aan de gegeven (x,y,z) vooraf gaat. Dat aantal kun je opdelen in:
- het aantal (x,y,k) met y<k<z
- het aantal (x,k,?) met x<k<y en alle mogelijke z
- het aantal (k,?,?) met k<x en alle mogelijke y en z
Dat tweede aantal kun je schrijven als de som van alle aantallen (x,k,?) van k=x+1 t/m y-1
Dat derde aantal kun je schrijven als een som van aantallen van het tweede type.

Als je dan die somreeks uitwerkt en vereenvoudigt (hulpmiddelen toegestaan ;)) krijg je bovenstaande formules.


Ja, het gaat inderdaad om het anatal combinaties welke VOORAF gaan aan een bepaalde combinatie.

Ik denk niet dat het hetzelfde is als "N+3" bv

N=10 -->

for x=1 to 10
for y=x+1 to 11
for z=y+1 to 12
pos = getindex(x,y,z,N)
next z
next y
next x

misshien ben ik mis, maar ik denk dat dit niet hetzelfde is als bij het verhogen van N

#9

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 09 december 2007 - 22:45

Uit die drie for loops kan ik niet bepalen wat je restricties precies zijn, of wat je eigenlijk probeert te doen. Heel vaak achter elkaar alleen een index uitrekenen doet niks he!

Maar gezien die for loops neem ik aan dat 1<x<y<z<13, vandaar dat het me dezelfde situatie lijkt als eerst met N+3 (dus N is nu 13).
In theory, there's no difference between theory and practice. In practice, there is.

#10

JackRnl

    JackRnl


  • 0 - 25 berichten
  • 15 berichten
  • Gebruiker

Geplaatst op 10 december 2007 - 17:33

Uit die drie for loops kan ik niet bepalen wat je restricties precies zijn, of wat je eigenlijk probeert te doen. Heel vaak achter elkaar alleen een index uitrekenen doet niks he!

Maar gezien die for loops neem ik aan dat 1<x<y<z<13, vandaar dat het me dezelfde situatie lijkt als eerst met N+3 (dus N is nu 13).



Bedankt voor je reacties Rogier ze hebben me geholpen.

Ik heb nu een werkend geheel waarmee ik de index van elke (x,y,z) kan berekenen (getest met waarden van 1-55 voor N)
Weliswaar niet geschreven als EEN formule, maar dat is 'eenvoudig' om te schrijven (laat ik echter zoals het is omdat dat duidelijker voor me is).

Uiteraard gaat het niet om heel vaak achter elkaar een index uit te rekenen, maar dit is gewoon een TESTprogramma om daadwerkelijk "iets" te kunnen terugvinden in een array op basis van de indexen (x,y,z) en het aantal N .
Dat heb ik nodig voor andere berekeningen die me veel te veel tijd (en memory) aan het doorzoeken van een grote array zouden kosten indien ik de volledige driedimensionale array zou opslaan (bij N=55 slechts 29260 i.p.v. 166375 elementen). In plaats van ZOEKEN wil ik VINDEN, daarom de indexberekening.

Hier het testprogrammaatje voor Excel

Sub test()
With Worksheets("Sheet1")
Record = 0
N = 10
For i1 = 1 To N
For i2 = i1 + 1 To N + 1
For i3 = i2 + 1 To N + 2
Pos = GetIndex(i1, i2, i3, N)
Record = Record + 1
.Cells(Record, 1) = Pos
.Cells(Record, 2) = i1
.Cells(Record, 3) = i2
.Cells(Record, 4) = i3
Next i3
Next i2
Next i1
End With
End Sub

Function GetIndex(xx, yy, zz, N) As Integer
x = xx - 1
y = yy - 1
z = zz - 1

H = N - x
H = ((H * (H + 1)) / 2) * (H + 2) / 3 '// Elements 1st index higher x
Part1 = (N * (N + 1) / 2) * (N + 2) / 3 - H '// Elements 1st index lower x
Part2 = (z - 1) + (y - 1) * N - (y - 1) * (1 + (y - 1)) / 2 '// Index combination (y,z)
Part3 = x * (N + 1) - x * (1 + x) / 2 '// Correction for 1st index on Part2
GetIndex = Part1 + Part2 - Part3
End Function





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures