c++ order range with values that doesn't fulfill strict weak ordering

how to set a range in c programming
switch case range c
how to set a range in c++ programming
c programming range of values
c++ check if number is in range
queries for counts of array elements with values in given range
switch case range java
switch case range c#

I need to order values in a range so the range represent a chain.

struct Link
{
   int id;
   int next;
};

The values of Link::id and Link::next are arbitrary, and do not provide any semantic meaning by them selves (not for the ordering algorithm any way).

The relationship between two links (after ordering) is: lhs.next is exactly rhs.id.

preconditions

  • The unordered range is guaranteed to hold values that can be ordered into exactly one chain.
  • It's guaranteed to be no recursion in the set of values (no loops)

Example:

std::vector< Link> range{ { 4, 1}, { 1, 5}, { 3, 4}, { 2, 3}};
auto chain = some_algorithm( range);
// expect the ordering to be: { { 2, 3}, { 3, 4}, { 4, 1}, { 1, 5}};

I can think of at least two approaches, but I suspect this has been solved in an idiomatic way. So, my question is: how to solve this in an idiomatic way?

I doubt that there is a idiomatic way because this isn't a common case.

Chaining is mostly done by pointers/iterators (e.g. std::list) and the actual chaining is mostly done while inserting.

The interesting thing would be to find the first link and what to do with circular chaining and with error cases.

Using range in switch case in C/C++, That is the case range extension of the GNU C compiler and not standard C or C​++; You can specify a range of consecutive values in a single case label, like  The first is the keys array and the second, the values array. Finally: The program prints out the keys array in its sorted order, and the values array in its sorted order. C# program that sorts keys and values using System; class Program { static void Main () { // Sort keys and values.

This is what I came up with:

The "concept" R is some type that that behaves range-like, could be a container, could be something else.

If there are gaps (link-wise) in the range, new chains will be ordered. I didn't want to have some "assert-output", or throwing. I still maintain my goals, since in my use-case I know all values can form exactly one chain.

  template< typename R, typename ISP>
  R chain( R range, ISP is_link_predicate)
  {
     auto first = std::begin( range);
     auto current = first;
     const auto last = std::end( range);

     while( current != last)
     {
        const auto next = current + 1;

        // try to find a value in [next, last) that can be linked with *current.
        auto link = std::find_if( next, last, [current,is_link_predicate]( auto& value){
           return is_link_predicate( *current, value);
        });

        if( link != last)
        {
           using std::swap;
           swap( *next, *link);
           current = next;
        }
        else
        {
           // we need to check if some value in [next, last) can be "inserted" in the
           // beginning of the chain. That is, can form a link with *first.
           auto new_first = std::find_if( next, last, [first,is_link_predicate]( auto& value){
              return is_link_predicate( value, *first);
           });

           if( new_first != last)
           {
              // we got a new_first, we need to rotate it first
              //
              // C = current
              // N = next (not ordered).
              // - = ordered values
              // = = not ordered values
              // X = value to be "inserted" first, new_first
              //
              // -----CN====X===  we start with
              // X-----C========  we end up with
              //
              std::rotate( first, new_first, new_first + 1);
              current = next;
           }
           else
           {
              // no values in [next, last) is part of the current chain.
              // we start building the next chain.
              current = next;
              first = current;
           }
        }
     }

     return range;
  }

Comments?

Queries for counts of array elements with values in given range , Time complexity for running each query will be O(n). C++. Unlike linspace, range doesn’t accept the number of elements in the tensor. Instead, it computes successive elements by adding a value called a delta . In the following code, delta is set to 0.5 :

First of all what you are doing is not sorting, so take your mind of sorting. You can never tell if A comes before or after B, you can just tell if A can be exactly 1 before or exactly 1 after B. So sorting cannot help you here, not even topological sorting.

An algorithm: for a chain A1..An backtrack through all elements X that can link with it, e.g. A1..AnX or XA1..An and repeat for the new chain. The starting chain is the empty one and any element can link with it.

Range-based for loop (since C++11), Used as a more readable equivalent to the traditional for loop operating over a range of values, such as all elements in a container. This example finds all cells in the range A1:A500 on worksheet one that contain the value 2, and changes it to 5. With Worksheets(1).Range("a1:a500") Set c = .Find(2, lookin:=xlValues) If Not c Is Nothing Then firstAddress = c.Address Do c.Value = 5 Set c = .FindNext(c) Loop While Not c Is Nothing End If End With

R: rank vs. order, you load data into a vector using the “c”ombine function; when you view X it Specifically the range of values returned by rank and order is the  If you want, you can overwrite this with a different range. Once you are satisfied that the values in the dialog box are correct, click OK. Excel will then create the new name Sales_Value that refers to the range B2-B5. Method 2: Create a Named Range Using the 'Create from Selection' Command

Talking Seriously About God, The numerical values that l, c and ci in fact have are accidental in the sense of the values could have been any other value from the ranges those values are to take on particular values that stand in particular ratios to each other in order for​  Python 3’s range uses the generator. Python 3’s range() will produce value when for loop iteration asked for it. i.e., it The range() doesn’t produce all numbers at once. Python range() function returns an immutable sequence object of integers, so its possible to convert range() output to python list.

Lookup and return multiple values sorted in a custom order, Lookup and return multiple values sorted in a custom order · Excel > Sort values Select cell G5; Copy cell (Ctrl + c); Select cell range G6:G11; Paste (Ctrl + v)  bool TestRange (int numberToCheck, int bottom, int top) { return (numberToCheck >= bottom && numberToCheck <= top); } Share a link to this answer. improve this answer. edited Sep 24 '15 at 15:12. 2 silver badges. 9 bronze badges. answered Jul 6 '10 at 17:32.

Comments
  • There are values for which some_algorithm has multiple solutions. How would you cope with, for instance, {1, 2}, {2, 3}, {3, 1}?
  • Out of curiosity, what would you expect if, rather than 2,3 that element were 5,3 ? In other words, wouldn't introducing a "loop", leave you with four possible sequences, all of which are correct (in that they fulfill your "chain" ? That alone suggests the restrictions of sorting algorithms (you must have a strict-weak ordering) in the standard library are not going to help you out here.
  • I'll update with preconditions. It's guaranteed to be no recursion in the value-set, and no "hops"/multiple chains.
  • @WhozCraig Yes, I know the standard algorithms demands strict-weak-ordering (for a good reason), that's why I'm asking this question :)
  • Look at Topological_sorting
  • I agree. I would build an unordered_map<int, Link> which maps an int to the Link with that id, and another which maps an int to the Link with that next. Then I would search all the Link's for the Link whose id is not a key in the next map - this is the first entry. Finally, having found the first entry, one just repeatedly finds the next entry by looking up next in the id map. Each individual operation is no worse than O(n log n), so the overall performance will be too (and it might be better than that).
  • I don't either think this is the common case. But, to me, it seams that this problem is not that far fetched, and someone, hopefully smarter than me, have given a lot of thoughts to this, hence my question :)
  • Personally, I wouldn't have bothered in trying to solve this in place. I would copy the links to a new range while first looking for a start of a chain and chaining from there until a new chain is needed. However, that doesn't mean my approach would be better, just more familiar to me. I would also have needed to invalidate copied links.
  • I was hoping to get some suggestions on improving the algorithm. Either to few finds this interesting or the algorithm is good enough. I'll mark this as the solution since it's working pretty good.
  • I know I'm not doing sorting, that's implicitly given by the fact that the values does not conform to strict weak ordering. Still there is an order to a chan, hence my question...
  • 'not even topological sorting'. After that, only checking we have a chain is needed.
  • @Jarod42 how can we apply topological sorting if we don't have a partial order? What am I missing?
  • We have partial ordering, with {4, 1} 4 happens before 1 or can also be seen as {4, 1} happens before any {1, X}. Then converting Link to Node/Egde might render some topological algorithms more adapted from others.
  • @Jarod42 I don't think you can say {4 1} happens before {1 7} because {1 7} {7 4} {4 1} is a valid chain.