Algorithms

Wjousts16-Jul-10 5:40

16-Jul-10 5:40

Well, I thought that too, but there is a problem with that. If I sort them by the left-most edge, then it's possible that the item with the highest left-most edge isn't the right-most object if there is another object that has a smaller left-most edge (i.e. is further to the left), but it wider such that it's right-most edge is actually more to the right. And the same is possible if you use right edges instead (but on the left-side instead).
So I'm not sure that there is a search criteria that will always guarantee that the first element with be the left-most and the last element will be the right-most.

   {-A-}                        {-B-}
{---C----}                     {---D---}

Example: if a sort by left-edge ({), C is the left-most element, and B is the right-most. If a sort by right-edges (}), A is the left most and D is the right-most. Neither of these is correct!

Alan Balkany16-Jul-10 5:50

16-Jul-10 5:50

As I suspected, the problem appears to be in the task definition.

From your description, it appears the most extreme coordinates are the most relevant. You might try sorting from the outside in:

1. Get the leftmost element, and make that the first item in your "sorted" list. (It's not a real sort, because what we have here is called a "partial order".)

2. Get the rightmost element, and make that the LAST item in the sorted list.

3. Get the second-leftmost element and make that the second item in the sorted list.

4. Get the second-rightmost element and make it the next-to-last item in the sorted list.

5. Repeat until you reach the middle item.

Wjousts20-Jul-10 3:31

20-Jul-10 3:31

An interesting idea. I might try that.

Wjousts20-Jul-10 7:56

20-Jul-10 7:56

I guess one place that technique might fall down would be if you had this:

....[A].......[B]..[C].....
..[..........D..........]..

Which when distributed should probably look like this:

.....[A]....[B]....[C].....
..[..........D..........]..

In this case D is both the left-most and right-most element!

Alan Balkany20-Jul-10 8:01

20-Jul-10 8:01

That's a consequence of treating a partial order like a total order.

If you want to try to sort these elements, D must either appear at the left or the right. The algorithm you design should reflect your goals, and if your goals are unclear it makes finding a solution many times harder.

Luc Pattyn16-Jul-10 5:54

16-Jul-10 5:54

I'm not sure what it is you want. Is this a two-dimensional problem? or are these objects grouped into N rows, so it becomes N 1-dimensional problems? I suggest you clarify by providing one or two examples with initial situation and probable solution. Using PRE tags (hence non-proportional font) should work fine.

AAA...BB
AAA...BB
......BB
CC......
CC..DDDD

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum

Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.

Alan Balkany16-Jul-10 6:06

16-Jul-10 6:06

It appears to be a two-dimensional problem, where each dimension can be treated independently, so it becomes two one-dimensional problems.

Wjousts20-Jul-10 3:30

20-Jul-10 3:30

I'm trying to implement functionality very similar to what PowerPoint does.
Example:

- Open PowerPoint
- On a blank slide, throw a bunch of boxes on the slide.
- Select several boxes.
- (In PowerPoint 2003, probably different in newer versions)Click Draw on the toolbar at the bottom, select "Align or Distribute" -> "Distribute Horizontally"

So, if you start with this (collapsing everything to one dimension for clarity):

....[A].....[B].....[C]..[D]...

You end up with this:

....[A]....[B]....[C]....[D]...

This is fairly trivial if all the boxes are the same size, but when they are different sizes, it gets a bit trickier (adding a second dimension only to make overlaps clearer - it's still a 1D problem):

.......[...B...]............[D]...
....[.A.]............[..C..]......

Should give:

..........[...B...].........[D]...
....[.A.]...........[..C..].......

Luc Pattyn20-Jul-10 8:11

20-Jul-10 8:11

if it is really one-dimensional, then it is trivial: the spaces should equal

( available_width - sum_of_widths_of_objects_in_row ) / ( number_of_objects_in_row - 1 )

it becomes interesting when it is actually a 2D problem, i.e. some blocks have multiple neighbours on one side, not all of the same width, as in:

AAAA......DD.....GGG
AAAA.............GGG
........CCCCCCC..GGG
BBBBBB..CCCCCCC..GGG
........CCCCCCC.....
EE..F...CCCCCCC...HH
....F.............HH
KKK.F....LLLL.....HH

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum

Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.

Wjousts20-Jul-10 9:14

20-Jul-10 9:14

Luc Pattyn wrote:
if it is really one-dimensional, then it is trivial: the spaces should equal

( available_width - sum_of_widths_of_objects_in_row ) / ( number_of_objects_in_row - 1 )

Yes, that's what I have described several posts above. That part isn't that complicated. What I want to do is find the most efficient way to actually implement it since (as described above) you have to find the left and right most boxes (which could be the same) first and then sort the boxes remaining boxes by their current position, then iterate through the set again actually setting the positions.
I thought there might be some clever shortcut to do it that I wasn't aware of.

Luc Pattyn20-Jul-10 9:38

Getting all combinations of N sets of objects iteratively

20-Jul-10 9:38

I would just sort their horizontal centers.

Smile | :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum

Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.

gantww11-Jul-10 15:58

gantww

11-Jul-10 15:58

Greetings,
I'm making a little utility app to dump out test data for my forays into neural network programming (to make the training data sets). I'm trying to make it a little easier to create test data sets, so I'm building this application that allows me to create a list of input fields (along with the range of their values). From that, I want the app to spit out a file that contains all the possible combinations of values that are available (I'm assuming that the sets of values are small, and not interrelated). I've got an abstract base class called BaseDataBuilder that simply contains a description and an abstract function that returns an IEnumerable<object> that represents the set of available values for a particular input field. I'm currently only inheriting from this class in another class called BooleanDataBuilder that has the following function that defines the available values:
public override IEnumerable<object> AvailableValues()
{
yield return true;
yield return false;
}

In the future, I'd like to have the flexibility to use this with other data types, but for the moment, I'm only considering booleans.

Further up, I have an object that contains a list of BaseDataBuilder objects (currently called DataBuilder, but I'll be changing the type name soon as it isn't descriptive). This object has the following function definition.

public IEnumerable<object[]> GetDataValues()
{

}

What I want this to return is essentially a set of rows that is a combination of all the available values as defined by the list of BaseDataBuilder objects. However, I'm kind of stuck as to how to implement this. I know I could do it using recursion, but I was hoping there was some sort of LINQ-ish type of way to do this.

Anybody have any ideas?

Re: Getting all combinations of N sets of objects iteratively

Alan Balkany15-Jul-10 3:55

15-Jul-10 3:55

For N input fields, define an N-bit binary number. As the number is incremented from all zeroes to all ones, the 1 bits in each number define all possible combinations of the N input fields. This is also called the "power set".

My sorting algorithm

AksharRoop6-Jul-10 4:53

AksharRoop

6-Jul-10 4:53

I have a list of values in single dimensional vector/array as follow:

{([point0, value0], [point1, value1], ... , [pointx, valuex]), ([pointx+1, valuex+1], [pointx+2, valuex+2], ... , [pointy, valuey]), ([pointy+1, valuey+1], [pointy+2, valuey+2], ... , [pointz, valuez])}

[at first it may look like weird how this is single dimentional array; but yes it is ]

{point0,value0,point1,value1,...,pointx,valuex}

Here i know how values are structured in an input array. I just need to implement best sorting technique for this. Requirement is to sort each block based on point value(i.e. sort point0,value0 to pointx,valuex). I have information about number of elements in each block (which will be consistent for all blocks). I can simply write something like:

<br />
// blockSize is given<br />
// totalBlocks size is given<br />
// setOfValues is given (to be sorted)

for(int blockIndex = 0 ; blockIndex  < totalBlocks; ++blockIndex)<br />
{<br />
 for(int i = blockSize * blockIndex; i < blockSize*(blockIndex + 1); i = i + 2)<br />
 {<br />
  for(int j = blockSize * blockIndex; j < blockSize*(blockIndex + 1); j = j + 2)<br />
  {	<br />
   if (setOfValues[i] < setOfValues[j])<br />
   {<br />
	int temp = setOfValues[i];<br />
	setOfValues[i] = setOfValues[j];<br />
        setOfValues[j] = temp;<br />
<br />
	temp = setOfValues[i+1];<br />
	setOfValues[i+1] = setOfValues[j+1];<br />
	setOfValues[j+1] = temp;<br />
   }<br />
  }<br />
 }<br />
}

Time required for this algorithm is very huge: O(totalBlocks * blockSize^2)

I am thinking of writing this in better way. Any help would be great!

Thanks,
AksharRoop

Luc Pattyn6-Jul-10 5:20

6-Jul-10 5:20

That is the worst sorting algorithm I've ever seen: you have chosen a poor data representation, picked the least sophisticated algorithm, and created a poor implementation.

For a general overview on sorting algorithms, read either this[^] or Knuth's book on the subject.

If your data were represented in a normal way (say an array of structs, each struct holding two ints), you could use the built-in Sort method which exists for arrays and all kinds of collections. Specifying the sorting criterium is explained here[^].

Smile | :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum

Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.

AksharRoop6-Jul-10 5:24

AksharRoop

6-Jul-10 5:24

I know Luc. But I have don't have other choice. I can't change the representation of data because it is sent further for some processing.

RugbyLeague6-Jul-10 22:41

RugbyLeague

6-Jul-10 22:41

How big is the data set? You could change it into something more suitable before using a better sorting algorithm then change it back once sorted.

I am not sure I get what your data is supposed to look like so it's difficult to suggest a sorting algorithm to work on it in its raw state.

molesworth7-Jul-10 1:33

molesworth

7-Jul-10 1:33

I don't think the data representation is the main problem here (unless they're large data structures) it's the choice of algorithm.

As already mentioned, it's probably the least efficient one possible...

Days spent at sea are not deducted from one's alloted span - Phoenician proverb