|
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.
|
|
|
|
|
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
|
|
|
|
|
It appears to be a two-dimensional problem, where each dimension can be treated independently, so it becomes two one-dimensional problems.
|
|
|
|
|
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..].......
|
|
|
|
|
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 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.
|
|
|
|
|
I would just sort their horizontal centers.
|
|
|
|
|
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?
|
|
|
|
|
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".
|
|
|
|
|
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 />
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
|
|
|
|
|
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[^].
|
|
|
|
|
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.
|
|
|
|
|
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.
|
|
|
|
|
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
|
|
|
|
|
I know - I just think it be easier for him to put the data into something more usable then sort on that using an appropriate algorithm out of the box rather than fiddling with an algorithm to use his data structure.
|
|
|
|
|
Any known methods here for counting the number of 'ON' bits in a bitmap?
Tadeusz Westawic
Sum quid sum.
|
|
|
|
|
What kind of "bitmap" do you mean?
The fastest way (excluding straight table lookup of course, but that only works well if the table is in cache) to count bits in an integer (without using the popcnt instruction, which is not commonly supported) is this: http://stackoverflow.com/posts/1511920/revisions[^]
It's based on this: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel[^]
edit: ok to clear the mess I made here up a bit..
There are many ways, including:
- popcnt: not supported by enough CPU's yet
- table lookup: only works well if you can keep the table in cache until you don't have to count any bits anymore, a cache miss is many time more terrible even than using the "standard" way (so if you have to count a lots of bits in a tight loop, go for it)
- count the bits one by one[^], works well if you expect few bits to be set (or reset - just take the complement and subtract the count from the length)
- count the bits in parallel (see links in the first part of my post) - it has no bad case, making it a safe choice. It simply uses a fixed number of steps, without needing big tables.
modified on Thursday, June 24, 2010 11:22 AM
|
|
|
|
|
Good links, thanks.
All bitmaps are mono.
I was thinking of taking the bits on a boolean swim to upper left of bm using bitblt()and then binary look for first zero row, etc. I don't have a swim algorihm though.
Does that get anyone's wheels turning?
*********START EDIT
Um, assume theoretical mono bitmaps so we avoid platform dependency and speed discussion. I can always xlate to MS at code time.
*********END EDIT
Tadeusz Westawic
Sum quid sum.
-- Modified Thursday, June 24, 2010 12:28 PM
|
|
|
|
|
Sorry, I have no idea what a swim algorithm is, google isn't being very helpful either..
|
|
|
|
|
A "theoretical mono bitmap"? How does it work? Just a grid of bools of unknown format - so tricks are out?
In that case you can't do any better than just test each pixel and increment a counter if the pixel is "true", that makes the question irrelevant so that probably isn't what you meant.
|
|
|
|
|
OK. "Swim" is my term to describe the motion of the bits in the bitmap (my wheel unsticks as I write).
In my actual code for other bitmap projects tricks are IN but only generic boolean blitting, no graphics languages per se but certainly take what a device interface gives. All need know are bm dims.
"Swim" would blit the lower portion of bm against the upper in binary shrinking row count.
Take OR blit to 'swim' all the bottom half bits to upper half bitmap.
Take AND on same two bitmaps to preserve the bits that could not swim due to collision with bits already in upper half.
.
.
Too fuzzy yet.
Tadeusz Westawic
Sum quid sum.
|
|
|
|
|
Well, that does not make sense to me. And you still haven't told why you would need a bit count.
|
|
|
|
|
What and why I count could be for any reason that yields meaningful results upon well-defined processing.
Can you do parallel swimming adders?
The generic term is 'collision counting' it is first related to 'collision detection'. Although the old raster arcade games employed these techniques extensively my work is not about games and accomodation in Windows is paltry; so lets say analysis where you want to count hits by vectors against a surface (in simplest form but my work is more mundane).
So, this problem implies we have some loci in discrete 3-space: the surface under test, and one each also for each projectile path, lets say 16 path locii.
Immediately map the discrete loci to congruent 2-space bitmaps, call the size (w x h).
Actuate three new bitmaps bmSRC, bmTGT and bmRSLT each (16w x 16h).
Tile bmSRC with 16 identical copies of the surface bm.
Tile bmTGT as mosaic of the 16 paths.
AND the bms into bmRSLT
The number of bits set in bmRSLT represents the number of paths intersecting the surface.
******************************
That looks like I solved 16 sets of simultaneous equations in parallel but if one needs to know "WHERE?" the collisions occurred then one is in need of an algorithm. So one does not employ thes techniques if one needs to know "WHERE?", but when the yes/no answer to "IF" will suffice.
You would also normally avoid "HOW MANY?", but in the case of a running model, one needs to benchmark and perform some "reality check" routines and count the actual number of bits to compare against a statistical projection.
Blit happens.
Tadeusz Westawic
Sum quid sum.
|
|
|
|
|
OK. It sounds like your bits are sparse then, so I'd go for a sequential count, probably like this (C#):
public int CountBits(uint[] data) {
int count=0;
foreach (uint dd in data) {
uint d=dd;
while(d!=0) {
count++;
d&=d-1;
}
}
return count;
}
or a table lookup, which works fine for bytes and maybe shorts (for 32-bit data you'd have to split in two or four bitgroups to keep the table small and cachable):
int[] bitCountInByte=new int[256];
public int CountBits(byte[] data) {
int count=0;
foreach (byte d in data) {
if (d!=0) count+=bitCountInByte[d];
}
return count;
}
|
|
|
|
|
I see.. I think.
If you also add NOT then you could build an adder out of that, I suppose..
That's a little weird though
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
