# Filling a Finite Vector Space

Page 1 of 1

## 9 Replies - 541 Views - Last Post: 23 July 2013 - 09:05 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=325480&amp;s=711e26bad5d72f5fec7c0a45016fafe4&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Korupt

Reputation: 21
• 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

• Code herder

Reputation: 4768
• Posts: 15,750
• 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;

```

### #3 Korupt

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

## Re: Filling a Finite Vector Space

Posted 23 July 2013 - 05:52 PM

Skydiver, 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

### #4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11758
• Posts: 44,175
• 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.

### #5 Korupt

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

## Re: Filling a Finite Vector Space

Posted 23 July 2013 - 06:05 PM

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

### #6 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11758
• Posts: 44,175
• 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

### #7 Korupt

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

## Re: Filling a Finite Vector Space

Posted 23 July 2013 - 06:42 PM

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

### #8 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11758
• Posts: 44,175
• 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

### #9 Korupt

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

## Re: Filling a Finite Vector Space

Posted 23 July 2013 - 08:42 PM

macosxnerd101, 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

### #10 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11758
• Posts: 44,175
• 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.