Combinatorics Question

Given a complete graph with nodes N:

Whats the most uniform way to traverse it for any non-triangular number N?

This has driven me insane for a couple of years now, is there even a solution?

Uniform in what way?

This question makes no sense.

If it's a complete graph, then any node connects to every other node. So you just look at all the edges of your current node. And suddenly you have traversed the graph.

>>3
It makes even less sense: there's no need to provide any traversal algorithm like you did, because all nodes in a complete graph are indistinguishable and therefore all traversals are isomorphic. In a sense there exists one traversal, if you ignore arbitrary way you might number the nodes.

>>4
well then I haven't figured out how to formulate the question.
Oh yes I numbered the nodes... so I'll try again:

A numbered structure (represented by an array in memory) should be accessed in such a order that every element should follow every other element the same number of times and the distance distribution between elements is as uniform as possible. (Every possible distance has to be represented, upwards and downwards, so the "complete graph" would be traversed 2 times one time "forward" one "backwards") I somehow came up to the conclusion that if the number of elements is a triangular number complete uniform "traversal" is possible, else not.

Major problem is: I do not have enough math education to formulate *exactly* what I am looking for but know what it is.

>>5
So, do you want to visit every edge (also, twice, in each direction)?

Show some traversals that do satisfy your requirements, please.

You're going to be a second tier and shit programmer as long as you don't know mathematics.

>>5
I feel like you are searching for things in a room with no lights on. I recommend that you study Introduction to Algorithms by Manber.

Or maybe go here (http://en.wikipedia.org/wiki/Eulerian_path) and follow the links. Learning about Eulerian tours might get you somewhere. I don't even know what the paragraph you wrote means.

Here's my interpretation.

For K₄ the path 0 ⇒ 1 ⇒ 3 ⇒ 2 is a solution because the differences between the vertices of each visited edge are 1, 2, 3 (mod 4), i.e. every natural number x with 0 < x < 4 is present once, and each vertex is visited once. The only other solution is the inverse 0 ⇒ 3 ⇒ 1 ⇒ 2 with differences 3, 2, 1. A path is a solution iff it's inverse is a solution.

K₁ and K₂ both have 1 (trivial) solution, K₃ and higher odd numbers seem to have no solution, K₆ has 4 solutions (diff 1, 4, 3, 2, 5), (diff 2, 5, 3, 1, 4) and their inverses. K₈ has 24 solutions, K₁₀ has 288 solutions, K₁₂ has 3856. This sequence is http://oeis.org/A141599

#lang racket

(require (planet wmfarr/permutations:1:3/permutations))

(define m 12)

(for/fold ((a 0)) ((l (in-permutations (- m 1))))
  (define z (make-vector m))
  (vector-set! z 0 0)
  (for ((i (in-range (- m 1))))
    (vector-set! z (+ i 1) (remainder (+ (vector-ref z i) (vector-ref l i) 1) m)))
;  (when (permutation? z) (printf "~a ~a~n" l z))
  (+ a (if (permutation? z) 1 0)))

>>7 what mathematics should I know?

Here we go again.

>>10
Set theory. You should also switch your major to Finance and/or Business.

>>10
EVERYTHING

Some basic CS topics: discrete mathematics (basic proofs, combinatorics etc). algorithms (data structures, graphs, general techniques, etc). computational theory (FSM, automata, etc).

>>13
PS. You have to learn all this to be at all decent at computer science..

>>14
Where do I  begin?

>>15

it would be ideal to get a good handle on discrete math, with proofs and combinatorics, and then check out algorithms, and then check out computational theory, but you could learn what some of these things are without too much knowledge of the previous categories. You just wouldn't be able to get too in depth with the proofs and results about them. But as they are, they are all pretty much just imaginary constructs that have pretty intuitive definitions. You could check out finite state machines (FSMs), what they are and what they are used for in software, and it is all pretty natural. Graphs are also nice like that. The proofs about them can become pretty complex, but they usually rely on a simple characteristic of their definition. You might want to get some familiarity with combinatorics before you get into the proofs and stuff in graph theory.

This stuff is all very beautiful, but I think a lot of coders are only familiar with what they are, and they would rather look up relevant information and not try to understand the reasons for why it all works.