9 Replies - 309 Views - Last Post: 23 July 2013 - 09:05 PM Rate Topic: -----

#1 Korupt  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 21
  • View blog
  • Posts: 185
  • Joined: 22-June 08

Filling a Finite Vector Space

Posted 23 July 2013 - 05:07 PM

This is more of a general algorithms question rather than a C question, but, since my code is written in C, I will post it here. I am doing math research in additive combinatorics/finite geometry, and I need to be able to fill up a vector space over a finite Glaois field. What this means is fairly simply, take, for example, the finite field of 3 elements GF(3)={0,1,2}, the one-dimensional vector space over GF(3) (denoted AG(1,3)) contains the points AG(1,3) = {(0),(1),(2)}, the two dimensional vector space of GF(3) contains the points AG(2,3) = {(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)} and so on for any dimension n. This is the code I have written for it, it it fills up the entire space with just ones, because I am not sure how to actually go about doing this,

typedef struct tuple {
	int n;
	int weight;
	int *data;
}n_tuple;

typedef struct space {
	int dim;
	int mod;
	int size;
	n_tuple *points;
}f_space;

f_space *createSpace(int dimension, int mod) {
	f_space *myspace = (f_space *)malloc(sizeof(f_space));

	if (myspace == NULL)
		return NULL;

	myspace->dim = dimension;
	myspace->mod = mod;
	myspace->size = pow(mod, dimension);
	myspace->points = (n_tuple *)malloc(sizeof(n_tuple)*myspace->size);

	if (myspace->points == NULL)
		return NULL;

	int i;
	int j;
	for (i = 0;i < myspace->size;i++) {
		myspace->points[i].n = dimension;
		myspace->points[i].data = (int *)malloc(sizeof(int)*dimension);

		if (myspace->points[i].data == NULL)
			return NULL;

		for (j = 0;j < dimension;j++) {
			myspace->points[i].data[j] = 1;
		}
	}

	return myspace;
}



Any help is appriciated. If there isn't an algorithm for n dimensions, a suggestion for one in a fixed dimension (say 3) is also welcome as I will simply hard code each dimension I need to work with. One thing I forgot to mention, in the code, the variable mod stands for the characteristic of the Galois field, so GF(mod) = {0,1,2,...,mod - 1}. Thank you.

This post has been edited by Korupt: 23 July 2013 - 05:10 PM


Is This A Good Question/Topic? 1
  • +

Replies To: Filling a Finite Vector Space

#2 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3469
  • View blog
  • Posts: 10,691
  • Joined: 05-May 12

Re: Filling a Finite Vector Space

Posted 23 July 2013 - 05:39 PM

It fills it with 1's because of your line 38:
38            myspace->points[i].data[j] = 1;


Was This Post Helpful? 1
  • +
  • -

#3 Korupt  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 21
  • View blog
  • Posts: 185
  • Joined: 22-June 08

Re: Filling a Finite Vector Space

Posted 23 July 2013 - 05:52 PM

View PostSkydiver, on 23 July 2013 - 08:39 PM, said:

It fills it with 1's because of your line 38:
38            myspace->points[i].data[j] = 1;



Haha, I am aware of that. Like I said, I am not sure how to go about this, so I just made it fill the space with 1(s). I need a way to fill the space with the actual values though. I can also re-state this problem as filling the following matrix automatically (this is for AG(3,3)),

int **three_space[27][3] = {0, 0, 0,
                            0, 0, 1,
                            0, 0, 2,
                            0, 1, 0,
                            0, 1, 1,
                            0, 1, 2,
                            0, 2, 0,
                            0, 2, 1,
                            0, 2, 2,
                            1, 0, 0,
                            1, 0, 1,
                            1, 0, 2,
                            1, 1, 0,
                            1, 1, 1,
                            1, 1, 2,
                            1, 2, 0,
                            1, 2, 1,
                            1, 2, 2,
                            2, 0, 0,
                            2, 0, 1,
                            2, 0, 2,
                            2, 1, 0,
                            2, 1, 1,
                            2, 1, 2,
                            2, 2, 0,
                            2, 2, 1,
                            2, 2, 2 };


This post has been edited by Korupt: 23 July 2013 - 06:08 PM

Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10390
  • View blog
  • Posts: 38,450
  • Joined: 27-December 08

Re: Filling a Finite Vector Space

Posted 23 July 2013 - 06:01 PM

Take this as a counting approach. If there are n ordered elements in the Field, you can count. So for your Galois Field {0, 1, 2}, count: 000, 001, 002, 010, 011, 012, 020, etc.
Was This Post Helpful? 1
  • +
  • -

#5 Korupt  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 21
  • View blog
  • Posts: 185
  • Joined: 22-June 08

Re: Filling a Finite Vector Space

Posted 23 July 2013 - 06:05 PM

View Postmacosxnerd101, on 23 July 2013 - 09:01 PM, said:

Take this as a counting approach. If there are n ordered elements in the Field, you can count. So for your Galois Field {0, 1, 2}, count: 000, 001, 002, 010, 011, 012, 020, etc.


Right that is the approach I would take if I was to write out these points manually, but I am not really sure how to put it in code.
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10390
  • View blog
  • Posts: 38,450
  • Joined: 27-December 08

Re: Filling a Finite Vector Space

Posted 23 July 2013 - 06:10 PM

Start with [0, 0, 0]. The next vector should increment the end element. If that element is greater than n, set it to 0 and increment the next element. So your index starts at length-1, then proceeds to 0 as necessary. If you increment an element at a given index and it is still less than n, then break. The last vector is [n-1, n-1, n-1].

So there are kn vectors in the vector space C(n, k) * k! vectors in the vector space, where C(n, k) represents the choose function.

This post has been edited by macosxnerd101: 23 July 2013 - 06:45 PM
Reason for edit:: Fixed formula

Was This Post Helpful? 1
  • +
  • -

#7 Korupt  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 21
  • View blog
  • Posts: 185
  • Joined: 22-June 08

Re: Filling a Finite Vector Space

Posted 23 July 2013 - 06:42 PM

View Postmacosxnerd101, on 23 July 2013 - 09:10 PM, said:

Start with [0, 0, 0]. The next vector should increment the end element. If that element is greater than n, set it to 0 and increment the next element. So your index starts at length-1, then proceeds to 0 as necessary. If you increment an element at a given index and it is still less than n, then break. The last vector is [n-1, n-1, n-1].

So there are C(n, k) * k! vectors in the vector space, where C(n, k) represents the choose function.


That's actually not true, for a space given as AG(n,k) (dimenstion n over GF(k)) there are k^n elements in the space, and I don't thin your formula simplifies down to that. Could you give me a bit of sample code in setting up the loops to do this, I've been at it for hours and my brain has basically melted, so I cannot come up with anything.
Was This Post Helpful? 1
  • +
  • -

#8 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10390
  • View blog
  • Posts: 38,450
  • Joined: 27-December 08

Re: Filling a Finite Vector Space

Posted 23 July 2013 - 06:49 PM

You're right! I've fixed the formula.

Some pseudo-code to point you in the right direction:
function nextVector(vector v, int n)
    vector next = new vector(v) //copy constructor
    for i = v.length-1; i >= 0; i--
        next[i] = (next[i] + 1) (mod n)
        if next[i] != 0
           break
    end for

    return next


This post has been edited by macosxnerd101: 23 July 2013 - 09:05 PM
Reason for edit:: Fixed pseudo-code

Was This Post Helpful? 1
  • +
  • -

#9 Korupt  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 21
  • View blog
  • Posts: 185
  • Joined: 22-June 08

Re: Filling a Finite Vector Space

Posted 23 July 2013 - 08:42 PM

View Postmacosxnerd101, on 23 July 2013 - 09:49 PM, said:

You're right! I've fixed the formula.

Some pseudo-code to point you in the right direction:
function nextVector(vector v, int n)
    vector next = new vector(v) //copy constructor
    for i = v.length-1; i > 0; i--
        next[i] = (next[i] + 1) (mod n)
        if next[i] != 0
           break
    end for

    return next



Thanks there was just a little error in your pseudo-code, the for loop should have the condition i >= 0 not i > 0. But I got it working, here is the C code if anyone is interested.

typedef struct tuple {
	int n;
	int weight;
	int *data;
}n_tuple;

typedef struct space {
	int dim;
	int mod;
	int size;
	n_tuple *points;
}f_space;

f_space *createSpace(int dimension, int mod) {
	f_space *myspace = (f_space *)malloc(sizeof(f_space));

	if (myspace == NULL)
		return NULL;

	myspace->dim = dimension;
	myspace->mod = mod;
	myspace->size = pow(mod, dimension);
	myspace->points = (n_tuple *)malloc(sizeof(n_tuple)*myspace->size);

	if (myspace->points == NULL)
		return NULL;

	//Instalize the first point
	myspace->points[0].n = dimension;
	myspace->points[0].data = (int *)malloc(sizeof(int)*dimension);
	if (myspace->points[0].data == NULL)
		return NULL;
	//Fill in the first point
	int i;
	for (i = 0;i < dimension;i++)
		myspace->points[0].data[i] = 0;


	int j;
	for (i = 1;i < myspace->size;i++) {
		myspace->points[i].n = dimension;
		myspace->points[i].data = (int *)malloc(sizeof(int)*dimension);

		if (myspace->points[i].data == NULL)
			return NULL;

		//Copy previous point
		for (j = 0;j < dimension;j++)
			myspace->points[i].data[j] = myspace->points[i-1].data[j];

		for (j = dimension - 1;j >= 0;j--) {
			myspace->points[i].data[j] = (myspace->points[i].data[j] + 1) % mod;
			if (myspace->points[i].data[j] != 0)
				break;
		}
	}
	return myspace;
}


This post has been edited by Korupt: 23 July 2013 - 08:58 PM

Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10390
  • View blog
  • Posts: 38,450
  • Joined: 27-December 08

Re: Filling a Finite Vector Space

Posted 23 July 2013 - 09:05 PM

Glad you got it working! Sorry for the little error.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1